1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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.HDFSBlocksDistribution;
44 import org.apache.hadoop.hbase.HRegionInfo;
45 import org.apache.hadoop.hbase.RegionLoad;
46 import org.apache.hadoop.hbase.ServerName;
47 import org.apache.hadoop.hbase.client.RegionReplicaUtil;
48 import org.apache.hadoop.hbase.master.LoadBalancer;
49 import org.apache.hadoop.hbase.master.MasterServices;
50 import org.apache.hadoop.hbase.master.RackManager;
51 import org.apache.hadoop.hbase.master.RegionPlan;
52 import org.apache.hadoop.hbase.master.balancer.BaseLoadBalancer.Cluster.Action.Type;
53 import org.apache.hadoop.util.StringUtils;
54
55 import com.google.common.annotations.VisibleForTesting;
56 import com.google.common.base.Joiner;
57 import com.google.common.collect.ArrayListMultimap;
58 import com.google.common.collect.Lists;
59 import com.google.common.collect.Sets;
60
61
62
63
64
65
66
67
68 public abstract class BaseLoadBalancer implements LoadBalancer {
69 private static final int MIN_SERVER_BALANCE = 2;
70 private volatile boolean stopped = false;
71
72 private static final List<HRegionInfo> EMPTY_REGION_LIST = new ArrayList<HRegionInfo>(0);
73
74 protected final RegionLocationFinder regionFinder = new RegionLocationFinder();
75
76 private static class DefaultRackManager extends RackManager {
77 @Override
78 public String getRack(ServerName server) {
79 return UNKNOWN_RACK;
80 }
81 }
82
83
84
85
86 protected BaseLoadBalancer() {
87 metricsBalancer = new MetricsBalancer();
88 }
89
90
91
92
93
94 protected BaseLoadBalancer(MetricsBalancer metricsBalancer) {
95 this.metricsBalancer = (metricsBalancer != null) ? metricsBalancer : new MetricsBalancer();
96 }
97
98
99
100
101
102
103
104
105
106
107
108 protected static class Cluster {
109 ServerName[] servers;
110 String[] hosts;
111 String[] racks;
112 boolean multiServersPerHost = false;
113
114 ArrayList<String> tables;
115 HRegionInfo[] regions;
116 Deque<RegionLoad>[] regionLoads;
117 private RegionLocationFinder regionFinder;
118
119 int[][] regionLocations;
120
121 int[] serverIndexToHostIndex;
122 int[] serverIndexToRackIndex;
123
124 int[][] regionsPerServer;
125 int[][] regionsPerHost;
126 int[][] regionsPerRack;
127 int[][] primariesOfRegionsPerServer;
128 int[][] primariesOfRegionsPerHost;
129 int[][] primariesOfRegionsPerRack;
130
131 int[][] serversPerHost;
132 int[][] serversPerRack;
133 int[] regionIndexToServerIndex;
134 int[] initialRegionIndexToServerIndex;
135 int[] regionIndexToTableIndex;
136 int[][] numRegionsPerServerPerTable;
137 int[] numMaxRegionsPerTable;
138 int[] regionIndexToPrimaryIndex;
139 boolean hasRegionReplicas = false;
140
141 Integer[] serverIndicesSortedByRegionCount;
142 Integer[] serverIndicesSortedByLocality;
143
144 Map<String, Integer> serversToIndex;
145 Map<String, Integer> hostsToIndex;
146 Map<String, Integer> racksToIndex;
147 Map<String, Integer> tablesToIndex;
148 Map<HRegionInfo, Integer> regionsToIndex;
149 float[] localityPerServer;
150
151 int numServers;
152 int numHosts;
153 int numRacks;
154 int numTables;
155 int numRegions;
156
157 int numMovedRegions = 0;
158 Map<ServerName, List<HRegionInfo>> clusterState;
159
160 protected final RackManager rackManager;
161
162 protected Cluster(
163 Map<ServerName, List<HRegionInfo>> clusterState,
164 Map<String, Deque<RegionLoad>> loads,
165 RegionLocationFinder regionFinder,
166 RackManager rackManager) {
167 this(null, clusterState, loads, regionFinder,
168 rackManager);
169 }
170
171 @SuppressWarnings("unchecked")
172 protected Cluster(
173 Collection<HRegionInfo> unassignedRegions,
174 Map<ServerName, List<HRegionInfo>> clusterState,
175 Map<String, Deque<RegionLoad>> loads,
176 RegionLocationFinder regionFinder,
177 RackManager rackManager) {
178
179 if (unassignedRegions == null) {
180 unassignedRegions = EMPTY_REGION_LIST;
181 }
182
183 serversToIndex = new HashMap<String, Integer>();
184 hostsToIndex = new HashMap<String, Integer>();
185 racksToIndex = new HashMap<String, Integer>();
186 tablesToIndex = new HashMap<String, Integer>();
187
188
189 tables = new ArrayList<String>();
190 this.rackManager = rackManager != null ? rackManager : new DefaultRackManager();
191
192 numRegions = 0;
193
194 List<List<Integer>> serversPerHostList = new ArrayList<List<Integer>>();
195 List<List<Integer>> serversPerRackList = new ArrayList<List<Integer>>();
196 this.clusterState = clusterState;
197 this.regionFinder = regionFinder;
198
199
200
201 for (ServerName sn : clusterState.keySet()) {
202 if (serversToIndex.get(sn.getHostAndPort()) == null) {
203 serversToIndex.put(sn.getHostAndPort(), numServers++);
204 }
205 if (!hostsToIndex.containsKey(sn.getHostname())) {
206 hostsToIndex.put(sn.getHostname(), numHosts++);
207 serversPerHostList.add(new ArrayList<Integer>(1));
208 }
209
210 int serverIndex = serversToIndex.get(sn.getHostAndPort());
211 int hostIndex = hostsToIndex.get(sn.getHostname());
212 serversPerHostList.get(hostIndex).add(serverIndex);
213
214 String rack = this.rackManager.getRack(sn);
215 if (!racksToIndex.containsKey(rack)) {
216 racksToIndex.put(rack, numRacks++);
217 serversPerRackList.add(new ArrayList<Integer>());
218 }
219 int rackIndex = racksToIndex.get(rack);
220 serversPerRackList.get(rackIndex).add(serverIndex);
221 }
222
223
224 for (Entry<ServerName, List<HRegionInfo>> entry : clusterState.entrySet()) {
225 numRegions += entry.getValue().size();
226 }
227 numRegions += unassignedRegions.size();
228
229 regionsToIndex = new HashMap<HRegionInfo, Integer>(numRegions);
230 servers = new ServerName[numServers];
231 serversPerHost = new int[numHosts][];
232 serversPerRack = new int[numRacks][];
233 regions = new HRegionInfo[numRegions];
234 regionIndexToServerIndex = new int[numRegions];
235 initialRegionIndexToServerIndex = new int[numRegions];
236 regionIndexToTableIndex = new int[numRegions];
237 regionIndexToPrimaryIndex = new int[numRegions];
238 regionLoads = new Deque[numRegions];
239 regionLocations = new int[numRegions][];
240 serverIndicesSortedByRegionCount = new Integer[numServers];
241 serverIndicesSortedByLocality = new Integer[numServers];
242 localityPerServer = new float[numServers];
243
244 serverIndexToHostIndex = new int[numServers];
245 serverIndexToRackIndex = new int[numServers];
246 regionsPerServer = new int[numServers][];
247 regionsPerHost = new int[numHosts][];
248 regionsPerRack = new int[numRacks][];
249 primariesOfRegionsPerServer = new int[numServers][];
250 primariesOfRegionsPerHost = new int[numHosts][];
251 primariesOfRegionsPerRack = new int[numRacks][];
252
253 int tableIndex = 0, regionIndex = 0, regionPerServerIndex = 0;
254
255 for (Entry<ServerName, List<HRegionInfo>> entry : clusterState.entrySet()) {
256 int serverIndex = serversToIndex.get(entry.getKey().getHostAndPort());
257
258
259
260 if (servers[serverIndex] == null ||
261 servers[serverIndex].getStartcode() < entry.getKey().getStartcode()) {
262 servers[serverIndex] = entry.getKey();
263 }
264
265 if (regionsPerServer[serverIndex] != null) {
266
267
268 regionsPerServer[serverIndex] = new int[entry.getValue().size() + regionsPerServer[serverIndex].length];
269 } else {
270 regionsPerServer[serverIndex] = new int[entry.getValue().size()];
271 }
272 primariesOfRegionsPerServer[serverIndex] = new int[regionsPerServer[serverIndex].length];
273 serverIndicesSortedByRegionCount[serverIndex] = serverIndex;
274 serverIndicesSortedByLocality[serverIndex] = serverIndex;
275 }
276
277 hosts = new String[numHosts];
278 for (Entry<String, Integer> entry : hostsToIndex.entrySet()) {
279 hosts[entry.getValue()] = entry.getKey();
280 }
281 racks = new String[numRacks];
282 for (Entry<String, Integer> entry : racksToIndex.entrySet()) {
283 racks[entry.getValue()] = entry.getKey();
284 }
285
286 for (Entry<ServerName, List<HRegionInfo>> entry : clusterState.entrySet()) {
287 int serverIndex = serversToIndex.get(entry.getKey().getHostAndPort());
288 regionPerServerIndex = 0;
289
290 int hostIndex = hostsToIndex.get(entry.getKey().getHostname());
291 serverIndexToHostIndex[serverIndex] = hostIndex;
292
293 int rackIndex = racksToIndex.get(this.rackManager.getRack(entry.getKey()));
294 serverIndexToRackIndex[serverIndex] = rackIndex;
295
296 for (HRegionInfo region : entry.getValue()) {
297 registerRegion(region, regionIndex, serverIndex, loads, regionFinder);
298
299 regionsPerServer[serverIndex][regionPerServerIndex++] = regionIndex;
300 regionIndex++;
301 }
302 }
303 for (HRegionInfo region : unassignedRegions) {
304 registerRegion(region, regionIndex, -1, loads, regionFinder);
305 regionIndex++;
306 }
307
308 for (int i = 0; i < serversPerHostList.size(); i++) {
309 serversPerHost[i] = new int[serversPerHostList.get(i).size()];
310 for (int j = 0; j < serversPerHost[i].length; j++) {
311 serversPerHost[i][j] = serversPerHostList.get(i).get(j);
312 }
313 if (serversPerHost[i].length > 1) {
314 multiServersPerHost = true;
315 }
316 }
317
318 for (int i = 0; i < serversPerRackList.size(); i++) {
319 serversPerRack[i] = new int[serversPerRackList.get(i).size()];
320 for (int j = 0; j < serversPerRack[i].length; j++) {
321 serversPerRack[i][j] = serversPerRackList.get(i).get(j);
322 }
323 }
324
325 numTables = tables.size();
326 numRegionsPerServerPerTable = new int[numServers][numTables];
327
328 for (int i = 0; i < numServers; i++) {
329 for (int j = 0; j < numTables; j++) {
330 numRegionsPerServerPerTable[i][j] = 0;
331 }
332 }
333
334 for (int i=0; i < regionIndexToServerIndex.length; i++) {
335 if (regionIndexToServerIndex[i] >= 0) {
336 numRegionsPerServerPerTable[regionIndexToServerIndex[i]][regionIndexToTableIndex[i]]++;
337 }
338 }
339
340 numMaxRegionsPerTable = new int[numTables];
341 for (int serverIndex = 0 ; serverIndex < numRegionsPerServerPerTable.length; serverIndex++) {
342 for (tableIndex = 0 ; tableIndex < numRegionsPerServerPerTable[serverIndex].length; tableIndex++) {
343 if (numRegionsPerServerPerTable[serverIndex][tableIndex] > numMaxRegionsPerTable[tableIndex]) {
344 numMaxRegionsPerTable[tableIndex] = numRegionsPerServerPerTable[serverIndex][tableIndex];
345 }
346 }
347 }
348
349 for (int i = 0; i < regions.length; i ++) {
350 HRegionInfo info = regions[i];
351 if (RegionReplicaUtil.isDefaultReplica(info)) {
352 regionIndexToPrimaryIndex[i] = i;
353 } else {
354 hasRegionReplicas = true;
355 HRegionInfo primaryInfo = RegionReplicaUtil.getRegionInfoForDefaultReplica(info);
356 regionIndexToPrimaryIndex[i] =
357 regionsToIndex.containsKey(primaryInfo) ?
358 regionsToIndex.get(primaryInfo):
359 -1;
360 }
361 }
362
363 for (int i = 0; i < regionsPerServer.length; i++) {
364 primariesOfRegionsPerServer[i] = new int[regionsPerServer[i].length];
365 for (int j = 0; j < regionsPerServer[i].length; j++) {
366 int primaryIndex = regionIndexToPrimaryIndex[regionsPerServer[i][j]];
367 primariesOfRegionsPerServer[i][j] = primaryIndex;
368 }
369
370 Arrays.sort(primariesOfRegionsPerServer[i]);
371 }
372
373
374 if (multiServersPerHost) {
375 for (int i = 0 ; i < serversPerHost.length; i++) {
376 int numRegionsPerHost = 0;
377 for (int j = 0; j < serversPerHost[i].length; j++) {
378 numRegionsPerHost += regionsPerServer[serversPerHost[i][j]].length;
379 }
380 regionsPerHost[i] = new int[numRegionsPerHost];
381 primariesOfRegionsPerHost[i] = new int[numRegionsPerHost];
382 }
383 for (int i = 0 ; i < serversPerHost.length; i++) {
384 int numRegionPerHostIndex = 0;
385 for (int j = 0; j < serversPerHost[i].length; j++) {
386 for (int k = 0; k < regionsPerServer[serversPerHost[i][j]].length; k++) {
387 int region = regionsPerServer[serversPerHost[i][j]][k];
388 regionsPerHost[i][numRegionPerHostIndex] = region;
389 int primaryIndex = regionIndexToPrimaryIndex[region];
390 primariesOfRegionsPerHost[i][numRegionPerHostIndex] = primaryIndex;
391 numRegionPerHostIndex++;
392 }
393 }
394
395 Arrays.sort(primariesOfRegionsPerHost[i]);
396 }
397 }
398
399
400 if (numRacks > 1) {
401 for (int i = 0 ; i < serversPerRack.length; i++) {
402 int numRegionsPerRack = 0;
403 for (int j = 0; j < serversPerRack[i].length; j++) {
404 numRegionsPerRack += regionsPerServer[serversPerRack[i][j]].length;
405 }
406 regionsPerRack[i] = new int[numRegionsPerRack];
407 primariesOfRegionsPerRack[i] = new int[numRegionsPerRack];
408 }
409
410 for (int i = 0 ; i < serversPerRack.length; i++) {
411 int numRegionPerRackIndex = 0;
412 for (int j = 0; j < serversPerRack[i].length; j++) {
413 for (int k = 0; k < regionsPerServer[serversPerRack[i][j]].length; k++) {
414 int region = regionsPerServer[serversPerRack[i][j]][k];
415 regionsPerRack[i][numRegionPerRackIndex] = region;
416 int primaryIndex = regionIndexToPrimaryIndex[region];
417 primariesOfRegionsPerRack[i][numRegionPerRackIndex] = primaryIndex;
418 numRegionPerRackIndex++;
419 }
420 }
421
422 Arrays.sort(primariesOfRegionsPerRack[i]);
423 }
424 }
425 }
426
427
428 private void registerRegion(HRegionInfo region, int regionIndex, int serverIndex,
429 Map<String, Deque<RegionLoad>> loads, RegionLocationFinder regionFinder) {
430 String tableName = region.getTable().getNameAsString();
431 if (!tablesToIndex.containsKey(tableName)) {
432 tables.add(tableName);
433 tablesToIndex.put(tableName, tablesToIndex.size());
434 }
435 int tableIndex = tablesToIndex.get(tableName);
436
437 regionsToIndex.put(region, regionIndex);
438 regions[regionIndex] = region;
439 regionIndexToServerIndex[regionIndex] = serverIndex;
440 initialRegionIndexToServerIndex[regionIndex] = serverIndex;
441 regionIndexToTableIndex[regionIndex] = tableIndex;
442
443
444 if (loads != null) {
445 Deque<RegionLoad> rl = loads.get(region.getRegionNameAsString());
446
447 if (rl == null) {
448
449 rl = loads.get(region.getEncodedName());
450 }
451 regionLoads[regionIndex] = rl;
452 }
453
454 if (regionFinder != null) {
455
456 List<ServerName> loc = regionFinder.getTopBlockLocations(region);
457 regionLocations[regionIndex] = new int[loc.size()];
458 for (int i=0; i < loc.size(); i++) {
459 regionLocations[regionIndex][i] =
460 loc.get(i) == null ? -1 :
461 (serversToIndex.get(loc.get(i).getHostAndPort()) == null ? -1
462 : serversToIndex.get(loc.get(i).getHostAndPort()));
463 }
464 }
465 }
466
467
468 public static class Action {
469 public static enum Type {
470 ASSIGN_REGION,
471 MOVE_REGION,
472 SWAP_REGIONS,
473 NULL,
474 }
475
476 public Type type;
477 public Action (Type type) {this.type = type;}
478
479 public Action undoAction() { return this; }
480 @Override
481 public String toString() { return type + ":";}
482 }
483
484 public static class AssignRegionAction extends Action {
485 public int region;
486 public int server;
487 public AssignRegionAction(int region, int server) {
488 super(Type.ASSIGN_REGION);
489 this.region = region;
490 this.server = server;
491 }
492 @Override
493 public Action undoAction() {
494
495
496 throw new NotImplementedException();
497 }
498 @Override
499 public String toString() {
500 return type + ": " + region + ":" + server;
501 }
502 }
503
504 public static class MoveRegionAction extends Action {
505 public int region;
506 public int fromServer;
507 public int toServer;
508
509 public MoveRegionAction(int region, int fromServer, int toServer) {
510 super(Type.MOVE_REGION);
511 this.fromServer = fromServer;
512 this.region = region;
513 this.toServer = toServer;
514 }
515 @Override
516 public Action undoAction() {
517 return new MoveRegionAction (region, toServer, fromServer);
518 }
519 @Override
520 public String toString() {
521 return type + ": " + region + ":" + fromServer + " -> " + toServer;
522 }
523 }
524
525 public static class SwapRegionsAction extends Action {
526 public int fromServer;
527 public int fromRegion;
528 public int toServer;
529 public int toRegion;
530 public SwapRegionsAction(int fromServer, int fromRegion, int toServer, int toRegion) {
531 super(Type.SWAP_REGIONS);
532 this.fromServer = fromServer;
533 this.fromRegion = fromRegion;
534 this.toServer = toServer;
535 this.toRegion = toRegion;
536 }
537 @Override
538 public Action undoAction() {
539 return new SwapRegionsAction (fromServer, toRegion, toServer, fromRegion);
540 }
541 @Override
542 public String toString() {
543 return type + ": " + fromRegion + ":" + fromServer + " <-> " + toRegion + ":" + toServer;
544 }
545 }
546
547 @edu.umd.cs.findbugs.annotations.SuppressWarnings(value="NM_FIELD_NAMING_CONVENTION",
548 justification="Mistake. Too disruptive to change now")
549 public static final Action NullAction = new Action(Type.NULL);
550
551 public void doAction(Action action) {
552 switch (action.type) {
553 case NULL: break;
554 case ASSIGN_REGION:
555
556 assert action instanceof AssignRegionAction: action.getClass();
557 AssignRegionAction ar = (AssignRegionAction) action;
558 regionsPerServer[ar.server] = addRegion(regionsPerServer[ar.server], ar.region);
559 regionMoved(ar.region, -1, ar.server);
560 break;
561 case MOVE_REGION:
562 assert action instanceof MoveRegionAction: action.getClass();
563 MoveRegionAction mra = (MoveRegionAction) action;
564 regionsPerServer[mra.fromServer] = removeRegion(regionsPerServer[mra.fromServer], mra.region);
565 regionsPerServer[mra.toServer] = addRegion(regionsPerServer[mra.toServer], mra.region);
566 regionMoved(mra.region, mra.fromServer, mra.toServer);
567 break;
568 case SWAP_REGIONS:
569 assert action instanceof SwapRegionsAction: action.getClass();
570 SwapRegionsAction a = (SwapRegionsAction) action;
571 regionsPerServer[a.fromServer] = replaceRegion(regionsPerServer[a.fromServer], a.fromRegion, a.toRegion);
572 regionsPerServer[a.toServer] = replaceRegion(regionsPerServer[a.toServer], a.toRegion, a.fromRegion);
573 regionMoved(a.fromRegion, a.fromServer, a.toServer);
574 regionMoved(a.toRegion, a.toServer, a.fromServer);
575 break;
576 default:
577 throw new RuntimeException("Uknown action:" + action.type);
578 }
579 }
580
581
582
583
584
585
586
587
588 boolean wouldLowerAvailability(HRegionInfo regionInfo, ServerName serverName) {
589 if (!serversToIndex.containsKey(serverName.getHostAndPort())) {
590 return false;
591 }
592 int server = serversToIndex.get(serverName.getHostAndPort());
593 int region = regionsToIndex.get(regionInfo);
594
595 int primary = regionIndexToPrimaryIndex[region];
596
597
598
599
600 if (contains(primariesOfRegionsPerServer[server], primary)) {
601
602 for (int i = 0; i < primariesOfRegionsPerServer.length; i++) {
603 if (i != server && !contains(primariesOfRegionsPerServer[i], primary)) {
604 return true;
605 }
606 }
607 return false;
608 }
609
610
611 if (multiServersPerHost) {
612 int host = serverIndexToHostIndex[server];
613 if (contains(primariesOfRegionsPerHost[host], primary)) {
614
615 for (int i = 0; i < primariesOfRegionsPerHost.length; i++) {
616 if (i != host && !contains(primariesOfRegionsPerHost[i], primary)) {
617 return true;
618 }
619 }
620 return false;
621 }
622 }
623
624
625 if (numRacks > 1) {
626 int rack = serverIndexToRackIndex[server];
627 if (contains(primariesOfRegionsPerRack[rack], primary)) {
628
629 for (int i = 0; i < primariesOfRegionsPerRack.length; i++) {
630 if (i != rack && !contains(primariesOfRegionsPerRack[i], primary)) {
631 return true;
632 }
633 }
634 return false;
635 }
636 }
637 return false;
638 }
639
640 void doAssignRegion(HRegionInfo regionInfo, ServerName serverName) {
641 if (!serversToIndex.containsKey(serverName.getHostAndPort())) {
642 return;
643 }
644 int server = serversToIndex.get(serverName.getHostAndPort());
645 int region = regionsToIndex.get(regionInfo);
646 doAction(new AssignRegionAction(region, server));
647 }
648
649 void regionMoved(int region, int oldServer, int newServer) {
650 regionIndexToServerIndex[region] = newServer;
651 if (initialRegionIndexToServerIndex[region] == newServer) {
652 numMovedRegions--;
653 } else if (oldServer >= 0 && initialRegionIndexToServerIndex[region] == oldServer) {
654 numMovedRegions++;
655 }
656 int tableIndex = regionIndexToTableIndex[region];
657 if (oldServer >= 0) {
658 numRegionsPerServerPerTable[oldServer][tableIndex]--;
659 }
660 numRegionsPerServerPerTable[newServer][tableIndex]++;
661
662
663 if (numRegionsPerServerPerTable[newServer][tableIndex] > numMaxRegionsPerTable[tableIndex]) {
664 numMaxRegionsPerTable[tableIndex] = numRegionsPerServerPerTable[newServer][tableIndex];
665 } else if (oldServer >= 0 && (numRegionsPerServerPerTable[oldServer][tableIndex] + 1)
666 == numMaxRegionsPerTable[tableIndex]) {
667
668 numMaxRegionsPerTable[tableIndex] = 0;
669 for (int serverIndex = 0 ; serverIndex < numRegionsPerServerPerTable.length; serverIndex++) {
670 if (numRegionsPerServerPerTable[serverIndex][tableIndex] > numMaxRegionsPerTable[tableIndex]) {
671 numMaxRegionsPerTable[tableIndex] = numRegionsPerServerPerTable[serverIndex][tableIndex];
672 }
673 }
674 }
675
676
677 int primary = regionIndexToPrimaryIndex[region];
678 if (oldServer >= 0) {
679 primariesOfRegionsPerServer[oldServer] = removeRegion(
680 primariesOfRegionsPerServer[oldServer], primary);
681 }
682 primariesOfRegionsPerServer[newServer] = addRegionSorted(
683 primariesOfRegionsPerServer[newServer], primary);
684
685
686 if (multiServersPerHost) {
687 int oldHost = oldServer >= 0 ? serverIndexToHostIndex[oldServer] : -1;
688 int newHost = serverIndexToHostIndex[newServer];
689 if (newHost != oldHost) {
690 regionsPerHost[newHost] = addRegion(regionsPerHost[newHost], region);
691 primariesOfRegionsPerHost[newHost] = addRegionSorted(primariesOfRegionsPerHost[newHost], primary);
692 if (oldHost >= 0) {
693 regionsPerHost[oldHost] = removeRegion(regionsPerHost[oldHost], region);
694 primariesOfRegionsPerHost[oldHost] = removeRegion(
695 primariesOfRegionsPerHost[oldHost], primary);
696 }
697 }
698 }
699
700
701 if (numRacks > 1) {
702 int oldRack = oldServer >= 0 ? serverIndexToRackIndex[oldServer] : -1;
703 int newRack = serverIndexToRackIndex[newServer];
704 if (newRack != oldRack) {
705 regionsPerRack[newRack] = addRegion(regionsPerRack[newRack], region);
706 primariesOfRegionsPerRack[newRack] = addRegionSorted(primariesOfRegionsPerRack[newRack], primary);
707 if (oldRack >= 0) {
708 regionsPerRack[oldRack] = removeRegion(regionsPerRack[oldRack], region);
709 primariesOfRegionsPerRack[oldRack] = removeRegion(
710 primariesOfRegionsPerRack[oldRack], primary);
711 }
712 }
713 }
714 }
715
716 int[] removeRegion(int[] regions, int regionIndex) {
717
718 int[] newRegions = new int[regions.length - 1];
719 int i = 0;
720 for (i = 0; i < regions.length; i++) {
721 if (regions[i] == regionIndex) {
722 break;
723 }
724 newRegions[i] = regions[i];
725 }
726 System.arraycopy(regions, i+1, newRegions, i, newRegions.length - i);
727 return newRegions;
728 }
729
730 int[] addRegion(int[] regions, int regionIndex) {
731 int[] newRegions = new int[regions.length + 1];
732 System.arraycopy(regions, 0, newRegions, 0, regions.length);
733 newRegions[newRegions.length - 1] = regionIndex;
734 return newRegions;
735 }
736
737 int[] addRegionSorted(int[] regions, int regionIndex) {
738 int[] newRegions = new int[regions.length + 1];
739 int i = 0;
740 for (i = 0; i < regions.length; i++) {
741 if (regions[i] > regionIndex) {
742 break;
743 }
744 }
745 System.arraycopy(regions, 0, newRegions, 0, i);
746 System.arraycopy(regions, i, newRegions, i+1, regions.length - i);
747 newRegions[i] = regionIndex;
748
749 return newRegions;
750 }
751
752 int[] replaceRegion(int[] regions, int regionIndex, int newRegionIndex) {
753 int i = 0;
754 for (i = 0; i < regions.length; i++) {
755 if (regions[i] == regionIndex) {
756 regions[i] = newRegionIndex;
757 break;
758 }
759 }
760 return regions;
761 }
762
763 void sortServersByRegionCount() {
764 Arrays.sort(serverIndicesSortedByRegionCount, numRegionsComparator);
765 }
766
767 int getNumRegions(int server) {
768 return regionsPerServer[server].length;
769 }
770
771 boolean contains(int[] arr, int val) {
772 return Arrays.binarySearch(arr, val) >= 0;
773 }
774
775 private Comparator<Integer> numRegionsComparator = new Comparator<Integer>() {
776 @Override
777 public int compare(Integer integer, Integer integer2) {
778 return Integer.compare(getNumRegions(integer), getNumRegions(integer2));
779 }
780 };
781
782 void sortServersByLocality() {
783 Arrays.sort(serverIndicesSortedByLocality, localityComparator);
784 }
785
786 float getLocality(int server) {
787 return localityPerServer[server];
788 }
789
790 private Comparator<Integer> localityComparator = new Comparator<Integer>() {
791 @Override
792 public int compare(Integer integer, Integer integer2) {
793 return Float.compare(getLocality(integer), getLocality(integer2));
794 }
795 };
796
797 int getLowestLocalityRegionServer() {
798 if (regionFinder == null) {
799 return -1;
800 } else {
801 sortServersByLocality();
802
803 int i = 0;
804 int lowestLocalityServerIndex = serverIndicesSortedByLocality[i];
805 while (localityPerServer[lowestLocalityServerIndex] == 0
806 && (regionsPerServer[lowestLocalityServerIndex].length == 0)) {
807 i++;
808 lowestLocalityServerIndex = serverIndicesSortedByLocality[i];
809 }
810 if (LOG.isTraceEnabled()) {
811 LOG.trace("Lowest locality region server with non zero regions is "
812 + servers[lowestLocalityServerIndex].getHostname() + " with locality "
813 + localityPerServer[lowestLocalityServerIndex]);
814 }
815 return lowestLocalityServerIndex;
816 }
817 }
818
819 int getLowestLocalityRegionOnServer(int serverIndex) {
820 if (regionFinder != null) {
821 float lowestLocality = 1.0f;
822 int lowestLocalityRegionIndex = -1;
823 if (regionsPerServer[serverIndex].length == 0) {
824
825 return -1;
826 }
827 for (int j = 0; j < regionsPerServer[serverIndex].length; j++) {
828 int regionIndex = regionsPerServer[serverIndex][j];
829 HDFSBlocksDistribution distribution = regionFinder
830 .getBlockDistribution(regions[regionIndex]);
831 float locality = distribution.getBlockLocalityIndex(servers[serverIndex].getHostname());
832
833 if (distribution.getUniqueBlocksTotalWeight() == 0) {
834 continue;
835 }
836 if (locality < lowestLocality) {
837 lowestLocality = locality;
838 lowestLocalityRegionIndex = j;
839 }
840 }
841 if (lowestLocalityRegionIndex == -1) {
842 return -1;
843 }
844 if (LOG.isTraceEnabled()) {
845 LOG.trace("Lowest locality region is "
846 + regions[regionsPerServer[serverIndex][lowestLocalityRegionIndex]]
847 .getRegionNameAsString() + " with locality " + lowestLocality
848 + " and its region server contains " + regionsPerServer[serverIndex].length
849 + " regions");
850 }
851 return regionsPerServer[serverIndex][lowestLocalityRegionIndex];
852 } else {
853 return -1;
854 }
855 }
856
857 float getLocalityOfRegion(int region, int server) {
858 if (regionFinder != null) {
859 HDFSBlocksDistribution distribution = regionFinder.getBlockDistribution(regions[region]);
860 return distribution.getBlockLocalityIndex(servers[server].getHostname());
861 } else {
862 return 0f;
863 }
864 }
865
866
867
868
869
870 int getLeastLoadedTopServerForRegion(int region, int currentServer) {
871 if (regionFinder != null) {
872 List<ServerName> topLocalServers = regionFinder.getTopBlockLocations(regions[region],
873 servers[currentServer].getHostname());
874 int leastLoadedServerIndex = -1;
875 int load = Integer.MAX_VALUE;
876 for (ServerName sn : topLocalServers) {
877 if (!serversToIndex.containsKey(sn.getHostAndPort())) {
878 continue;
879 }
880 int index = serversToIndex.get(sn.getHostAndPort());
881 if (regionsPerServer[index] == null) {
882 continue;
883 }
884 int tempLoad = regionsPerServer[index].length;
885 if (tempLoad <= load) {
886 leastLoadedServerIndex = index;
887 load = tempLoad;
888 }
889 }
890 if (leastLoadedServerIndex != -1) {
891 if (LOG.isTraceEnabled()) {
892 LOG.trace(
893 "Pick the least loaded server " + servers[leastLoadedServerIndex].getHostname()
894 + " with better locality for region " + regions[region]);
895 }
896 }
897 return leastLoadedServerIndex;
898 } else {
899 return -1;
900 }
901 }
902
903 void calculateRegionServerLocalities() {
904 if (regionFinder == null) {
905 LOG.warn("Region location finder found null, skipping locality calculations.");
906 return;
907 }
908 for (int i = 0; i < regionsPerServer.length; i++) {
909 HDFSBlocksDistribution distribution = new HDFSBlocksDistribution();
910 if (regionsPerServer[i].length > 0) {
911 for (int j = 0; j < regionsPerServer[i].length; j++) {
912 int regionIndex = regionsPerServer[i][j];
913 distribution.add(regionFinder.getBlockDistribution(regions[regionIndex]));
914 }
915 } else {
916 LOG.debug("Server " + servers[i].getHostname() + " had 0 regions.");
917 }
918 localityPerServer[i] = distribution.getBlockLocalityIndex(servers[i].getHostname());
919 }
920 }
921
922 @VisibleForTesting
923 protected void setNumRegions(int numRegions) {
924 this.numRegions = numRegions;
925 }
926
927 @VisibleForTesting
928 protected void setNumMovedRegions(int numMovedRegions) {
929 this.numMovedRegions = numMovedRegions;
930 }
931
932 @edu.umd.cs.findbugs.annotations.SuppressWarnings(value="SBSC_USE_STRINGBUFFER_CONCATENATION",
933 justification="Not important but should be fixed")
934 @Override
935 public String toString() {
936 String desc = "Cluster{" +
937 "servers=[";
938 for(ServerName sn:servers) {
939 desc += sn.getHostAndPort() + ", ";
940 }
941 desc +=
942 ", serverIndicesSortedByRegionCount="+
943 Arrays.toString(serverIndicesSortedByRegionCount) +
944 ", regionsPerServer=[";
945
946 for (int[]r:regionsPerServer) {
947 desc += Arrays.toString(r);
948 }
949 desc += "]" +
950 ", numMaxRegionsPerTable=" +
951 Arrays.toString(numMaxRegionsPerTable) +
952 ", numRegions=" +
953 numRegions +
954 ", numServers=" +
955 numServers +
956 ", numTables=" +
957 numTables +
958 ", numMovedRegions=" +
959 numMovedRegions +
960 '}';
961 return desc;
962 }
963 }
964
965
966 protected float slop;
967 protected Configuration config;
968 protected RackManager rackManager;
969 private static final Random RANDOM = new Random(System.currentTimeMillis());
970 private static final Log LOG = LogFactory.getLog(BaseLoadBalancer.class);
971
972 public static final String TABLES_ON_MASTER =
973 "hbase.balancer.tablesOnMaster";
974
975 protected final Set<String> tablesOnMaster = new HashSet<String>();
976 protected MetricsBalancer metricsBalancer = null;
977 protected ClusterStatus clusterStatus = null;
978 protected ServerName masterServerName;
979 @edu.umd.cs.findbugs.annotations.SuppressWarnings(value="IS2_INCONSISTENT_SYNC",
980 justification="The services is just assigned once when master start")
981 protected MasterServices services;
982
983 protected static String[] getTablesOnMaster(Configuration conf) {
984 String valueString = conf.get(TABLES_ON_MASTER);
985 if (valueString != null) {
986 valueString = valueString.trim();
987 }
988 if (valueString == null || valueString.equalsIgnoreCase("none")) {
989 return null;
990 }
991 return StringUtils.getStrings(valueString);
992 }
993
994
995
996
997 public static boolean tablesOnMaster(Configuration conf) {
998 String[] tables = getTablesOnMaster(conf);
999 return tables != null && tables.length > 0;
1000 }
1001
1002 public static boolean userTablesOnMaster(Configuration conf) {
1003 String[] tables = getTablesOnMaster(conf);
1004 if (tables == null || tables.length == 0) {
1005 return false;
1006 }
1007 for (String tn:tables) {
1008 if (!tn.startsWith("hbase:")) {
1009 return true;
1010 }
1011 }
1012 return false;
1013 }
1014
1015 @Override
1016 public void setConf(Configuration conf) {
1017 setSlop(conf);
1018 if (slop < 0) slop = 0;
1019 else if (slop > 1) slop = 1;
1020
1021 this.config = conf;
1022 String[] tables = getTablesOnMaster(conf);
1023 if (tables != null && tables.length > 0) {
1024 Collections.addAll(tablesOnMaster, tables);
1025 }
1026 this.rackManager = new RackManager(getConf());
1027 regionFinder.setConf(conf);
1028 }
1029
1030 protected void setSlop(Configuration conf) {
1031 this.slop = conf.getFloat("hbase.regions.slop", (float) 0.2);
1032 }
1033
1034
1035
1036
1037
1038 public boolean shouldBeOnMaster(HRegionInfo region) {
1039 return tablesOnMaster.contains(region.getTable().getNameAsString())
1040 && region.getReplicaId() == HRegionInfo.DEFAULT_REPLICA_ID;
1041 }
1042
1043
1044
1045
1046 protected List<RegionPlan> balanceMasterRegions(
1047 Map<ServerName, List<HRegionInfo>> clusterMap) {
1048 if (masterServerName == null
1049 || clusterMap == null || clusterMap.size() <= 1) return null;
1050 List<RegionPlan> plans = null;
1051 List<HRegionInfo> regions = clusterMap.get(masterServerName);
1052 if (regions != null) {
1053 Iterator<ServerName> keyIt = null;
1054 for (HRegionInfo region: regions) {
1055 if (shouldBeOnMaster(region)) continue;
1056
1057
1058 if (keyIt == null || !keyIt.hasNext()) {
1059 keyIt = clusterMap.keySet().iterator();
1060 }
1061 ServerName dest = keyIt.next();
1062 if (masterServerName.equals(dest)) {
1063 if (!keyIt.hasNext()) {
1064 keyIt = clusterMap.keySet().iterator();
1065 }
1066 dest = keyIt.next();
1067 }
1068
1069
1070 RegionPlan plan = new RegionPlan(region, masterServerName, dest);
1071 if (plans == null) {
1072 plans = new ArrayList<RegionPlan>();
1073 }
1074 plans.add(plan);
1075 }
1076 }
1077 for (Map.Entry<ServerName, List<HRegionInfo>> server: clusterMap.entrySet()) {
1078 if (masterServerName.equals(server.getKey())) continue;
1079 for (HRegionInfo region: server.getValue()) {
1080 if (!shouldBeOnMaster(region)) continue;
1081
1082
1083 RegionPlan plan = new RegionPlan(region, server.getKey(), masterServerName);
1084 if (plans == null) {
1085 plans = new ArrayList<RegionPlan>();
1086 }
1087 plans.add(plan);
1088 }
1089 }
1090 return plans;
1091 }
1092
1093
1094
1095
1096 protected Map<ServerName, List<HRegionInfo>> assignMasterRegions(
1097 Collection<HRegionInfo> regions, List<ServerName> servers) {
1098 if (servers == null || regions == null || regions.isEmpty()) {
1099 return null;
1100 }
1101 Map<ServerName, List<HRegionInfo>> assignments
1102 = new TreeMap<ServerName, List<HRegionInfo>>();
1103 if (masterServerName != null && servers.contains(masterServerName)) {
1104 assignments.put(masterServerName, new ArrayList<HRegionInfo>());
1105 for (HRegionInfo region: regions) {
1106 if (shouldBeOnMaster(region)) {
1107 assignments.get(masterServerName).add(region);
1108 }
1109 }
1110 }
1111 return assignments;
1112 }
1113
1114 @Override
1115 public Configuration getConf() {
1116 return this.config;
1117 }
1118
1119 @Override
1120 public synchronized void setClusterStatus(ClusterStatus st) {
1121 this.clusterStatus = st;
1122 regionFinder.setClusterStatus(st);
1123 }
1124
1125 @Override
1126 public void setMasterServices(MasterServices masterServices) {
1127 masterServerName = masterServices.getServerName();
1128 this.services = masterServices;
1129 this.regionFinder.setServices(masterServices);
1130 }
1131
1132 @Override
1133 public void postMasterStartupInitialize() {
1134 if (services != null && regionFinder != null) {
1135 try {
1136 Set<HRegionInfo> regions =
1137 services.getAssignmentManager().getRegionStates().getRegionAssignments().keySet();
1138 regionFinder.refreshAndWait(regions);
1139 } catch (Exception e) {
1140 LOG.warn("Refreshing region HDFS Block dist failed with exception, ignoring", e);
1141 }
1142 }
1143 }
1144
1145 public void setRackManager(RackManager rackManager) {
1146 this.rackManager = rackManager;
1147 }
1148
1149 protected boolean needsBalance(Cluster c) {
1150 ClusterLoadState cs = new ClusterLoadState(c.clusterState);
1151 if (cs.getNumServers() < MIN_SERVER_BALANCE) {
1152 if (LOG.isDebugEnabled()) {
1153 LOG.debug("Not running balancer because only " + cs.getNumServers()
1154 + " active regionserver(s)");
1155 }
1156 return false;
1157 }
1158 if(areSomeRegionReplicasColocated(c)) return true;
1159
1160
1161 float average = cs.getLoadAverage();
1162 int floor = (int) Math.floor(average * (1 - slop));
1163 int ceiling = (int) Math.ceil(average * (1 + slop));
1164 if (!(cs.getMaxLoad() > ceiling || cs.getMinLoad() < floor)) {
1165 NavigableMap<ServerAndLoad, List<HRegionInfo>> serversByLoad = cs.getServersByLoad();
1166 if (LOG.isTraceEnabled()) {
1167
1168 LOG.trace("Skipping load balancing because balanced cluster; " +
1169 "servers=" + cs.getNumServers() +
1170 " regions=" + cs.getNumRegions() + " average=" + average +
1171 " mostloaded=" + serversByLoad.lastKey().getLoad() +
1172 " leastloaded=" + serversByLoad.firstKey().getLoad());
1173 }
1174 return false;
1175 }
1176 return true;
1177 }
1178
1179
1180
1181
1182
1183
1184
1185
1186 protected boolean areSomeRegionReplicasColocated(Cluster c) {
1187 return false;
1188 }
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207 @Override
1208 public Map<ServerName, List<HRegionInfo>> roundRobinAssignment(List<HRegionInfo> regions,
1209 List<ServerName> servers) {
1210 metricsBalancer.incrMiscInvocations();
1211 Map<ServerName, List<HRegionInfo>> assignments = assignMasterRegions(regions, servers);
1212 if (assignments != null && !assignments.isEmpty()) {
1213 servers = new ArrayList<ServerName>(servers);
1214
1215 servers.remove(masterServerName);
1216 List<HRegionInfo> masterRegions = assignments.get(masterServerName);
1217 if (!masterRegions.isEmpty()) {
1218 regions = new ArrayList<HRegionInfo>(regions);
1219 for (HRegionInfo region: masterRegions) {
1220 regions.remove(region);
1221 }
1222 }
1223 }
1224 if (regions == null || regions.isEmpty()) {
1225 return assignments;
1226 }
1227
1228 int numServers = servers == null ? 0 : servers.size();
1229 if (numServers == 0) {
1230 LOG.warn("Wanted to do round robin assignment but no servers to assign to");
1231 return null;
1232 }
1233
1234
1235
1236
1237
1238
1239 if (numServers == 1) {
1240 ServerName server = servers.get(0);
1241 assignments.put(server, new ArrayList<HRegionInfo>(regions));
1242 return assignments;
1243 }
1244
1245 Cluster cluster = createCluster(servers, regions);
1246 List<HRegionInfo> unassignedRegions = new ArrayList<HRegionInfo>();
1247
1248 roundRobinAssignment(cluster, regions, unassignedRegions,
1249 servers, assignments);
1250
1251 List<HRegionInfo> lastFewRegions = new ArrayList<HRegionInfo>();
1252
1253 int serverIdx = RANDOM.nextInt(numServers);
1254 for (HRegionInfo region : unassignedRegions) {
1255 boolean assigned = false;
1256 for (int j = 0; j < numServers; j++) {
1257 ServerName serverName = servers.get((j + serverIdx) % numServers);
1258 if (!cluster.wouldLowerAvailability(region, serverName)) {
1259 List<HRegionInfo> serverRegions = assignments.get(serverName);
1260 if (serverRegions == null) {
1261 serverRegions = new ArrayList<HRegionInfo>();
1262 assignments.put(serverName, serverRegions);
1263 }
1264 serverRegions.add(region);
1265 cluster.doAssignRegion(region, serverName);
1266 serverIdx = (j + serverIdx + 1) % numServers;
1267 assigned = true;
1268 break;
1269 }
1270 }
1271 if (!assigned) {
1272 lastFewRegions.add(region);
1273 }
1274 }
1275
1276
1277 for (HRegionInfo region : lastFewRegions) {
1278 int i = RANDOM.nextInt(numServers);
1279 ServerName server = servers.get(i);
1280 List<HRegionInfo> serverRegions = assignments.get(server);
1281 if (serverRegions == null) {
1282 serverRegions = new ArrayList<HRegionInfo>();
1283 assignments.put(server, serverRegions);
1284 }
1285 serverRegions.add(region);
1286 cluster.doAssignRegion(region, server);
1287 }
1288 return assignments;
1289 }
1290
1291 protected Cluster createCluster(List<ServerName> servers, Collection<HRegionInfo> regions) {
1292
1293
1294
1295
1296 Map<ServerName, List<HRegionInfo>> clusterState = getRegionAssignmentsByServer(regions);
1297
1298 for (ServerName server : servers) {
1299 if (!clusterState.containsKey(server)) {
1300 clusterState.put(server, EMPTY_REGION_LIST);
1301 }
1302 }
1303 return new Cluster(regions, clusterState, null, this.regionFinder,
1304 rackManager);
1305 }
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324 @Override
1325 public Map<HRegionInfo, ServerName> immediateAssignment(List<HRegionInfo> regions,
1326 List<ServerName> servers) {
1327 metricsBalancer.incrMiscInvocations();
1328 if (servers == null || servers.isEmpty()) {
1329 LOG.warn("Wanted to do random assignment but no servers to assign to");
1330 return null;
1331 }
1332
1333 Map<HRegionInfo, ServerName> assignments = new TreeMap<HRegionInfo, ServerName>();
1334 for (HRegionInfo region : regions) {
1335 assignments.put(region, randomAssignment(region, servers));
1336 }
1337 return assignments;
1338 }
1339
1340
1341
1342
1343 @Override
1344 public ServerName randomAssignment(HRegionInfo regionInfo, List<ServerName> servers) {
1345 metricsBalancer.incrMiscInvocations();
1346 if (servers != null && servers.contains(masterServerName)) {
1347 if (shouldBeOnMaster(regionInfo)) {
1348 return masterServerName;
1349 }
1350 servers = new ArrayList<ServerName>(servers);
1351
1352 servers.remove(masterServerName);
1353 }
1354
1355 int numServers = servers == null ? 0 : servers.size();
1356 if (numServers == 0) {
1357 LOG.warn("Wanted to do retain assignment but no servers to assign to");
1358 return null;
1359 }
1360 if (numServers == 1) {
1361 return servers.get(0);
1362 }
1363
1364 List<HRegionInfo> regions = Lists.newArrayList(regionInfo);
1365 Cluster cluster = createCluster(servers, regions);
1366 return randomAssignment(cluster, regionInfo, servers);
1367 }
1368
1369
1370
1371
1372
1373
1374
1375
1376
1377
1378
1379
1380
1381
1382
1383
1384
1385
1386 @Override
1387 public Map<ServerName, List<HRegionInfo>> retainAssignment(Map<HRegionInfo, ServerName> regions,
1388 List<ServerName> servers) {
1389
1390 metricsBalancer.incrMiscInvocations();
1391 Map<ServerName, List<HRegionInfo>> assignments
1392 = assignMasterRegions(regions.keySet(), servers);
1393 if (assignments != null && !assignments.isEmpty()) {
1394 servers = new ArrayList<ServerName>(servers);
1395
1396 servers.remove(masterServerName);
1397 List<HRegionInfo> masterRegions = assignments.get(masterServerName);
1398 if (!masterRegions.isEmpty()) {
1399 regions = new HashMap<HRegionInfo, ServerName>(regions);
1400 for (HRegionInfo region: masterRegions) {
1401 regions.remove(region);
1402 }
1403 }
1404 }
1405 if (regions == null || regions.isEmpty()) {
1406 return assignments;
1407 }
1408
1409 int numServers = servers == null ? 0 : servers.size();
1410 if (numServers == 0) {
1411 LOG.warn("Wanted to do retain assignment but no servers to assign to");
1412 return null;
1413 }
1414 if (numServers == 1) {
1415 ServerName server = servers.get(0);
1416 assignments.put(server, new ArrayList<HRegionInfo>(regions.keySet()));
1417 return assignments;
1418 }
1419
1420
1421
1422
1423
1424
1425
1426 ArrayListMultimap<String, ServerName> serversByHostname = ArrayListMultimap.create();
1427 for (ServerName server : servers) {
1428 assignments.put(server, new ArrayList<HRegionInfo>());
1429 serversByHostname.put(server.getHostname(), server);
1430 }
1431
1432
1433
1434
1435 Set<String> oldHostsNoLongerPresent = Sets.newTreeSet();
1436
1437
1438 List<HRegionInfo> randomAssignRegions = Lists.newArrayList();
1439
1440 int numRandomAssignments = 0;
1441 int numRetainedAssigments = 0;
1442
1443 for (Map.Entry<HRegionInfo, ServerName> entry : regions.entrySet()) {
1444 HRegionInfo region = entry.getKey();
1445 ServerName oldServerName = entry.getValue();
1446 List<ServerName> localServers = new ArrayList<ServerName>();
1447 if (oldServerName != null) {
1448 localServers = serversByHostname.get(oldServerName.getHostname());
1449 }
1450 if (localServers.isEmpty()) {
1451
1452 randomAssignRegions.add(region);
1453 if (oldServerName != null) {
1454 oldHostsNoLongerPresent.add(oldServerName.getHostname());
1455 }
1456 } else if (localServers.size() == 1) {
1457
1458 ServerName target = localServers.get(0);
1459 assignments.get(target).add(region);
1460 numRetainedAssigments++;
1461 } else {
1462
1463 if (localServers.contains(oldServerName)) {
1464 assignments.get(oldServerName).add(region);
1465 numRetainedAssigments++;
1466 } else {
1467 ServerName target = null;
1468 for (ServerName tmp : localServers) {
1469 if (tmp.getPort() == oldServerName.getPort()) {
1470 target = tmp;
1471 assignments.get(tmp).add(region);
1472 numRetainedAssigments++;
1473 break;
1474 }
1475 }
1476 if (target == null) {
1477 randomAssignRegions.add(region);
1478 }
1479 }
1480 }
1481 }
1482
1483
1484 if (randomAssignRegions.size() > 0) {
1485 Cluster cluster = createCluster(servers, regions.keySet());
1486 for (Map.Entry<ServerName, List<HRegionInfo>> entry : assignments.entrySet()) {
1487 ServerName sn = entry.getKey();
1488 for (HRegionInfo region : entry.getValue()) {
1489 cluster.doAssignRegion(region, sn);
1490 }
1491 }
1492 for (HRegionInfo region : randomAssignRegions) {
1493 ServerName target = randomAssignment(cluster, region, servers);
1494 assignments.get(target).add(region);
1495 cluster.doAssignRegion(region, target);
1496 numRandomAssignments++;
1497 }
1498 }
1499
1500 String randomAssignMsg = "";
1501 if (numRandomAssignments > 0) {
1502 randomAssignMsg =
1503 numRandomAssignments + " regions were assigned "
1504 + "to random hosts, since the old hosts for these regions are no "
1505 + "longer present in the cluster. These hosts were:\n "
1506 + Joiner.on("\n ").join(oldHostsNoLongerPresent);
1507 }
1508
1509 LOG.info("Reassigned " + regions.size() + " regions. " + numRetainedAssigments
1510 + " retained the pre-restart assignment. " + randomAssignMsg);
1511 return assignments;
1512 }
1513
1514 @Override
1515 public void initialize() throws HBaseIOException{
1516 }
1517
1518 @Override
1519 public void regionOnline(HRegionInfo regionInfo, ServerName sn) {
1520 }
1521
1522 @Override
1523 public void regionOffline(HRegionInfo regionInfo) {
1524 }
1525
1526 @Override
1527 public boolean isStopped() {
1528 return stopped;
1529 }
1530
1531 @Override
1532 public void stop(String why) {
1533 LOG.info("Load Balancer stop requested: "+why);
1534 stopped = true;
1535 }
1536
1537
1538
1539
1540 public void updateBalancerStatus(boolean status) {
1541 metricsBalancer.balancerStatus(status);
1542 }
1543
1544
1545
1546
1547 private ServerName randomAssignment(Cluster cluster, HRegionInfo regionInfo,
1548 List<ServerName> servers) {
1549 int numServers = servers.size();
1550 ServerName sn = null;
1551 final int maxIterations = numServers * 4;
1552 int iterations = 0;
1553
1554 do {
1555 int i = RANDOM.nextInt(numServers);
1556 sn = servers.get(i);
1557 } while (cluster.wouldLowerAvailability(regionInfo, sn)
1558 && iterations++ < maxIterations);
1559 cluster.doAssignRegion(regionInfo, sn);
1560 return sn;
1561 }
1562
1563
1564
1565
1566 private void roundRobinAssignment(Cluster cluster, List<HRegionInfo> regions,
1567 List<HRegionInfo> unassignedRegions, List<ServerName> servers,
1568 Map<ServerName, List<HRegionInfo>> assignments) {
1569
1570 int numServers = servers.size();
1571 int numRegions = regions.size();
1572 int max = (int) Math.ceil((float) numRegions / numServers);
1573 int serverIdx = 0;
1574 if (numServers > 1) {
1575 serverIdx = RANDOM.nextInt(numServers);
1576 }
1577 int regionIdx = 0;
1578
1579 for (int j = 0; j < numServers; j++) {
1580 ServerName server = servers.get((j + serverIdx) % numServers);
1581 List<HRegionInfo> serverRegions = new ArrayList<HRegionInfo>(max);
1582 for (int i = regionIdx; i < numRegions; i += numServers) {
1583 HRegionInfo region = regions.get(i % numRegions);
1584 if (cluster.wouldLowerAvailability(region, server)) {
1585 unassignedRegions.add(region);
1586 } else {
1587 serverRegions.add(region);
1588 cluster.doAssignRegion(region, server);
1589 }
1590 }
1591 assignments.put(server, serverRegions);
1592 regionIdx++;
1593 }
1594 }
1595
1596 protected Map<ServerName, List<HRegionInfo>> getRegionAssignmentsByServer(
1597 Collection<HRegionInfo> regions) {
1598 if (this.services != null && this.services.getAssignmentManager() != null) {
1599 return this.services.getAssignmentManager().getSnapShotOfAssignment(regions);
1600 } else {
1601 return new HashMap<ServerName, List<HRegionInfo>>();
1602 }
1603 }
1604
1605 @Override
1606 public void onConfigurationChange(Configuration conf) {
1607 }
1608 }