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.Comparator;
23 import java.util.HashMap;
24 import java.util.List;
25 import java.util.Map;
26 import java.util.Map.Entry;
27 import java.util.Random;
28 import java.util.Set;
29 import java.util.TreeMap;
30 import java.util.NavigableMap;
31
32 import org.apache.commons.logging.Log;
33 import org.apache.commons.logging.LogFactory;
34 import org.apache.hadoop.conf.Configuration;
35 import org.apache.hadoop.hbase.ClusterStatus;
36 import org.apache.hadoop.hbase.HRegionInfo;
37 import org.apache.hadoop.hbase.RegionLoad;
38 import org.apache.hadoop.hbase.ServerName;
39 import org.apache.hadoop.hbase.master.AssignmentManager;
40 import org.apache.hadoop.hbase.master.LoadBalancer;
41 import org.apache.hadoop.hbase.master.MasterServices;
42 import org.apache.hadoop.hbase.util.Bytes;
43
44 import com.google.common.base.Joiner;
45 import com.google.common.collect.ArrayListMultimap;
46 import com.google.common.collect.Sets;
47
48
49
50
51
52
53
54 public abstract class BaseLoadBalancer implements LoadBalancer {
55
56
57
58
59
60
61 protected static class Cluster {
62 ServerName[] servers;
63 ArrayList<String> tables;
64 HRegionInfo[] regions;
65 List<RegionLoad>[] regionLoads;
66 int[][] regionLocations;
67
68 int[][] regionsPerServer;
69 int[] regionIndexToServerIndex;
70 int[] initialRegionIndexToServerIndex;
71 int[] regionIndexToTableIndex;
72 int[][] numRegionsPerServerPerTable;
73 int[] numMaxRegionsPerTable;
74
75 Integer[] serverIndicesSortedByRegionCount;
76
77 Map<String, Integer> serversToIndex;
78 Map<String, Integer> tablesToIndex;
79
80 int numRegions;
81 int numServers;
82 int numTables;
83
84 int numMovedRegions = 0;
85 int numMovedMetaRegions = 0;
86
87 protected Cluster(Map<ServerName, List<HRegionInfo>> clusterState, Map<String, List<RegionLoad>> loads,
88 RegionLocationFinder regionFinder) {
89
90 serversToIndex = new HashMap<String, Integer>();
91 tablesToIndex = new HashMap<String, Integer>();
92
93
94
95 tables = new ArrayList<String>();
96
97
98 numRegions = 0;
99
100 int serverIndex = 0;
101
102
103
104 for (ServerName sn:clusterState.keySet()) {
105 if (serversToIndex.get(sn.getHostAndPort()) == null) {
106 serversToIndex.put(sn.getHostAndPort(), serverIndex++);
107 }
108 }
109
110
111 for (Entry<ServerName, List<HRegionInfo>> entry : clusterState.entrySet()) {
112 numRegions += entry.getValue().size();
113 }
114
115 numServers = serversToIndex.size();
116 regionsPerServer = new int[serversToIndex.size()][];
117
118 servers = new ServerName[numServers];
119 regions = new HRegionInfo[numRegions];
120 regionIndexToServerIndex = new int[numRegions];
121 initialRegionIndexToServerIndex = new int[numRegions];
122 regionIndexToTableIndex = new int[numRegions];
123 regionLoads = new List[numRegions];
124 regionLocations = new int[numRegions][];
125 serverIndicesSortedByRegionCount = new Integer[numServers];
126
127 int tableIndex = 0, regionIndex = 0, regionPerServerIndex = 0;
128
129 for (Entry<ServerName, List<HRegionInfo>> entry : clusterState.entrySet()) {
130 serverIndex = serversToIndex.get(entry.getKey().getHostAndPort());
131
132
133
134 if (servers[serverIndex] == null ||
135 servers[serverIndex].getStartcode() < entry.getKey().getStartcode()) {
136 servers[serverIndex] = entry.getKey();
137 }
138
139 regionsPerServer[serverIndex] = new int[entry.getValue().size()];
140 serverIndicesSortedByRegionCount[serverIndex] = serverIndex;
141 }
142
143 for (Entry<ServerName, List<HRegionInfo>> entry : clusterState.entrySet()) {
144 serverIndex = serversToIndex.get(entry.getKey().getHostAndPort());
145 regionPerServerIndex = 0;
146
147 for (HRegionInfo region : entry.getValue()) {
148 String tableName = region.getTableNameAsString();
149 Integer idx = tablesToIndex.get(tableName);
150 if (idx == null) {
151 tables.add(tableName);
152 idx = tableIndex;
153 tablesToIndex.put(tableName, tableIndex++);
154 }
155
156 regions[regionIndex] = region;
157 regionIndexToServerIndex[regionIndex] = serverIndex;
158 initialRegionIndexToServerIndex[regionIndex] = serverIndex;
159 regionIndexToTableIndex[regionIndex] = idx;
160 regionsPerServer[serverIndex][regionPerServerIndex++] = regionIndex;
161
162
163 if (loads != null) {
164 List<RegionLoad> rl = loads.get(region.getRegionNameAsString());
165
166 if (rl == null) {
167
168 rl = loads.get(region.getEncodedName());
169 }
170 regionLoads[regionIndex] = rl;
171 }
172
173 if (regionFinder != null) {
174
175 List<ServerName> loc = regionFinder.getTopBlockLocations(region);
176 regionLocations[regionIndex] = new int[loc.size()];
177 for (int i=0; i < loc.size(); i++) {
178 regionLocations[regionIndex][i] =
179 loc.get(i) == null ? -1 :
180 (serversToIndex.get(loc.get(i)) == null ? -1 : serversToIndex.get(loc.get(i)));
181 }
182 }
183
184 regionIndex++;
185 }
186 }
187
188 numTables = tables.size();
189 numRegionsPerServerPerTable = new int[numServers][numTables];
190
191 for (int i = 0; i < numServers; i++) {
192 for (int j = 0; j < numTables; j++) {
193 numRegionsPerServerPerTable[i][j] = 0;
194 }
195 }
196
197 for (int i=0; i < regionIndexToServerIndex.length; i++) {
198 numRegionsPerServerPerTable[regionIndexToServerIndex[i]][regionIndexToTableIndex[i]]++;
199 }
200
201 numMaxRegionsPerTable = new int[numTables];
202 for (serverIndex = 0 ; serverIndex < numRegionsPerServerPerTable.length; serverIndex++) {
203 for (tableIndex = 0 ; tableIndex < numRegionsPerServerPerTable[serverIndex].length; tableIndex++) {
204 if (numRegionsPerServerPerTable[serverIndex][tableIndex] > numMaxRegionsPerTable[tableIndex]) {
205 numMaxRegionsPerTable[tableIndex] = numRegionsPerServerPerTable[serverIndex][tableIndex];
206 }
207 }
208 }
209 }
210
211 public void moveOrSwapRegion(int lServer, int rServer, int lRegion, int rRegion) {
212
213 if (rRegion >= 0 && lRegion >= 0) {
214 regionMoved(rRegion, rServer, lServer);
215 regionsPerServer[rServer] = replaceRegion(regionsPerServer[rServer], rRegion, lRegion);
216 regionMoved(lRegion, lServer, rServer);
217 regionsPerServer[lServer] = replaceRegion(regionsPerServer[lServer], lRegion, rRegion);
218 } else if (rRegion >= 0) {
219 regionMoved(rRegion, rServer, lServer);
220 regionsPerServer[rServer] = removeRegion(regionsPerServer[rServer], rRegion);
221 regionsPerServer[lServer] = addRegion(regionsPerServer[lServer], rRegion);
222 } else if (lRegion >= 0) {
223 regionMoved(lRegion, lServer, rServer);
224 regionsPerServer[lServer] = removeRegion(regionsPerServer[lServer], lRegion);
225 regionsPerServer[rServer] = addRegion(regionsPerServer[rServer], lRegion);
226 }
227 }
228
229
230 void regionMoved(int regionIndex, int oldServerIndex, int newServerIndex) {
231 regionIndexToServerIndex[regionIndex] = newServerIndex;
232 if (initialRegionIndexToServerIndex[regionIndex] == newServerIndex) {
233 numMovedRegions--;
234 if (regions[regionIndex].isMetaRegion()) {
235 numMovedMetaRegions--;
236 }
237 } else if (initialRegionIndexToServerIndex[regionIndex] == oldServerIndex) {
238 numMovedRegions++;
239 if (regions[regionIndex].isMetaRegion()) {
240 numMovedMetaRegions++;
241 }
242 }
243 int tableIndex = regionIndexToTableIndex[regionIndex];
244 numRegionsPerServerPerTable[oldServerIndex][tableIndex]--;
245 numRegionsPerServerPerTable[newServerIndex][tableIndex]++;
246
247
248 if (numRegionsPerServerPerTable[newServerIndex][tableIndex] > numMaxRegionsPerTable[tableIndex]) {
249 numRegionsPerServerPerTable[newServerIndex][tableIndex] = numMaxRegionsPerTable[tableIndex];
250 } else if ((numRegionsPerServerPerTable[oldServerIndex][tableIndex] + 1)
251 == numMaxRegionsPerTable[tableIndex]) {
252
253 for (int serverIndex = 0 ; serverIndex < numRegionsPerServerPerTable.length; serverIndex++) {
254 if (numRegionsPerServerPerTable[serverIndex][tableIndex] > numMaxRegionsPerTable[tableIndex]) {
255 numMaxRegionsPerTable[tableIndex] = numRegionsPerServerPerTable[serverIndex][tableIndex];
256 }
257 }
258 }
259 }
260
261 int[] removeRegion(int[] regions, int regionIndex) {
262
263 int[] newRegions = new int[regions.length - 1];
264 int i = 0;
265 for (i = 0; i < regions.length; i++) {
266 if (regions[i] == regionIndex) {
267 break;
268 }
269 newRegions[i] = regions[i];
270 }
271 System.arraycopy(regions, i+1, newRegions, i, newRegions.length - i);
272 return newRegions;
273 }
274
275 int[] addRegion(int[] regions, int regionIndex) {
276 int[] newRegions = new int[regions.length + 1];
277 System.arraycopy(regions, 0, newRegions, 0, regions.length);
278 newRegions[newRegions.length - 1] = regionIndex;
279 return newRegions;
280 }
281
282 int[] replaceRegion(int[] regions, int regionIndex, int newRegionIndex) {
283 int i = 0;
284 for (i = 0; i < regions.length; i++) {
285 if (regions[i] == regionIndex) {
286 regions[i] = newRegionIndex;
287 break;
288 }
289 }
290 return regions;
291 }
292
293 void sortServersByRegionCount() {
294 Arrays.sort(serverIndicesSortedByRegionCount, numRegionsComparator);
295 }
296
297 int getNumRegions(int server) {
298 return regionsPerServer[server].length;
299 }
300
301 private Comparator<Integer> numRegionsComparator = new Comparator<Integer>() {
302 @Override
303 public int compare(Integer integer, Integer integer2) {
304 return Integer.valueOf(getNumRegions(integer)).compareTo(getNumRegions(integer2));
305 }
306 };
307
308 @Override
309 public String toString() {
310 String desc = "Cluster{" +
311 "servers=[";
312 for(ServerName sn:servers) {
313 desc += sn.getHostAndPort() + ", ";
314 }
315 desc +=
316 ", serverIndicesSortedByRegionCount="+
317 Arrays.toString(serverIndicesSortedByRegionCount) +
318 ", regionsPerServer=[";
319
320 for (int[]r:regionsPerServer) {
321 desc += Arrays.toString(r);
322 }
323 desc += "]" +
324 ", numMaxRegionsPerTable=" +
325 Arrays.toString(numMaxRegionsPerTable) +
326 ", numRegions=" +
327 numRegions +
328 ", numServers=" +
329 numServers +
330 ", numTables=" +
331 numTables +
332 ", numMovedRegions=" +
333 numMovedRegions +
334 ", numMovedMetaRegions=" +
335 numMovedMetaRegions +
336 '}';
337 return desc;
338 }
339 }
340
341
342 private float slop;
343 private Configuration config;
344 private static final Random RANDOM = new Random(System.currentTimeMillis());
345 private static final Log LOG = LogFactory.getLog(BaseLoadBalancer.class);
346 protected MasterServices services;
347
348 @Override
349 public void setConf(Configuration conf) {
350 this.slop = conf.getFloat("hbase.regions.slop", (float) 0.2);
351 if (slop < 0) slop = 0;
352 else if (slop > 1) slop = 1;
353 this.config = conf;
354 }
355
356 @Override
357 public Configuration getConf() {
358 return this.config;
359 }
360
361 public void setClusterStatus(ClusterStatus st) {
362
363 }
364
365 public void setMasterServices(MasterServices masterServices) {
366 this.services = masterServices;
367 }
368
369 protected boolean needsBalance(ClusterLoadState cs) {
370 if (cs.getNumServers() == 0) {
371 LOG.debug("numServers=0 so skipping load balancing");
372 return false;
373 }
374
375
376 float average = cs.getLoadAverage();
377 int floor = (int) Math.floor(average * (1 - slop));
378 int ceiling = (int) Math.ceil(average * (1 + slop));
379 if (!(cs.getMinLoad() > ceiling || cs.getMaxLoad() < floor)) {
380 NavigableMap<ServerAndLoad, List<HRegionInfo>> serversByLoad = cs.getServersByLoad();
381 if (LOG.isTraceEnabled()) {
382
383 LOG.trace("Skipping load balancing because balanced cluster; " +
384 "servers=" + cs.getNumServers() + " " +
385 "regions=" + cs.getNumRegions() + " average=" + average + " " +
386 "mostloaded=" + serversByLoad.lastKey().getLoad() +
387 " leastloaded=" + serversByLoad.firstKey().getLoad());
388 }
389 return false;
390 }
391 return true;
392 }
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411 public Map<ServerName, List<HRegionInfo>> roundRobinAssignment(List<HRegionInfo> regions,
412 List<ServerName> servers) {
413 if (regions.isEmpty() || servers.isEmpty()) {
414 return null;
415 }
416 Map<ServerName, List<HRegionInfo>> assignments = new TreeMap<ServerName, List<HRegionInfo>>();
417 int numRegions = regions.size();
418 int numServers = servers.size();
419 int max = (int) Math.ceil((float) numRegions / numServers);
420 int serverIdx = 0;
421 if (numServers > 1) {
422 serverIdx = RANDOM.nextInt(numServers);
423 }
424 int regionIdx = 0;
425 for (int j = 0; j < numServers; j++) {
426 ServerName server = servers.get((j + serverIdx) % numServers);
427 List<HRegionInfo> serverRegions = new ArrayList<HRegionInfo>(max);
428 for (int i = regionIdx; i < numRegions; i += numServers) {
429 serverRegions.add(regions.get(i % numRegions));
430 }
431 assignments.put(server, serverRegions);
432 regionIdx++;
433 }
434 return assignments;
435 }
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454 public Map<HRegionInfo, ServerName> immediateAssignment(List<HRegionInfo> regions,
455 List<ServerName> servers) {
456 Map<HRegionInfo, ServerName> assignments = new TreeMap<HRegionInfo, ServerName>();
457 for (HRegionInfo region : regions) {
458 assignments.put(region, randomAssignment(region, servers));
459 }
460 return assignments;
461 }
462
463
464
465
466 public ServerName randomAssignment(HRegionInfo regionInfo, List<ServerName> servers) {
467 if (servers == null || servers.isEmpty()) {
468 LOG.warn("Wanted to do random assignment but no servers to assign to");
469 return null;
470 }
471 return servers.get(RANDOM.nextInt(servers.size()));
472 }
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491 public Map<ServerName, List<HRegionInfo>> retainAssignment(Map<HRegionInfo, ServerName> regions,
492 List<ServerName> servers) {
493
494
495
496
497
498
499 ArrayListMultimap<String, ServerName> serversByHostname = ArrayListMultimap.create();
500 for (ServerName server : servers) {
501 serversByHostname.put(server.getHostname(), server);
502 }
503
504
505 Map<ServerName, List<HRegionInfo>> assignments = new TreeMap<ServerName, List<HRegionInfo>>();
506
507 for (ServerName server : servers) {
508 assignments.put(server, new ArrayList<HRegionInfo>());
509 }
510
511
512
513
514 Set<String> oldHostsNoLongerPresent = Sets.newTreeSet();
515
516 int numRandomAssignments = 0;
517 int numRetainedAssigments = 0;
518 for (Map.Entry<HRegionInfo, ServerName> entry : regions.entrySet()) {
519 HRegionInfo region = entry.getKey();
520 ServerName oldServerName = entry.getValue();
521 List<ServerName> localServers = new ArrayList<ServerName>();
522 if (oldServerName != null) {
523 localServers = serversByHostname.get(oldServerName.getHostname());
524 }
525 if (localServers.isEmpty()) {
526
527
528 ServerName randomServer = servers.get(RANDOM.nextInt(servers.size()));
529 assignments.get(randomServer).add(region);
530 numRandomAssignments++;
531 if (oldServerName != null) oldHostsNoLongerPresent.add(oldServerName.getHostname());
532 } else if (localServers.size() == 1) {
533
534 assignments.get(localServers.get(0)).add(region);
535 numRetainedAssigments++;
536 } else {
537
538 int size = localServers.size();
539 ServerName target = localServers.get(RANDOM.nextInt(size));
540 assignments.get(target).add(region);
541 numRetainedAssigments++;
542 }
543 }
544
545 String randomAssignMsg = "";
546 if (numRandomAssignments > 0) {
547 randomAssignMsg =
548 numRandomAssignments + " regions were assigned "
549 + "to random hosts, since the old hosts for these regions are no "
550 + "longer present in the cluster. These hosts were:\n "
551 + Joiner.on("\n ").join(oldHostsNoLongerPresent);
552 }
553
554 LOG.info("Reassigned " + regions.size() + " regions. " + numRetainedAssigments
555 + " retained the pre-restart assignment. " + randomAssignMsg);
556 return assignments;
557 }
558
559 }