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 static org.junit.Assert.assertNotNull;
21 import static org.junit.Assert.assertNull;
22 import static org.junit.Assert.assertTrue;
23
24 import java.util.ArrayList;
25 import java.util.HashMap;
26 import java.util.HashSet;
27 import java.util.LinkedList;
28 import java.util.List;
29 import java.util.Map;
30 import java.util.Map.Entry;
31 import java.util.Queue;
32 import java.util.Random;
33 import java.util.Set;
34 import java.util.SortedSet;
35 import java.util.TreeMap;
36 import java.util.TreeSet;
37
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.HBaseConfiguration;
42 import org.apache.hadoop.hbase.HRegionInfo;
43 import org.apache.hadoop.hbase.ServerName;
44 import org.apache.hadoop.hbase.TableName;
45 import org.apache.hadoop.hbase.client.RegionReplicaUtil;
46 import org.apache.hadoop.hbase.master.RackManager;
47 import org.apache.hadoop.hbase.master.RegionPlan;
48 import org.apache.hadoop.hbase.util.Bytes;
49 import org.apache.hadoop.net.DNSToSwitchMapping;
50 import org.junit.Assert;
51 import org.junit.BeforeClass;
52
53
54
55
56
57
58
59 public class BalancerTestBase {
60 private static final Log LOG = LogFactory.getLog(BalancerTestBase.class);
61 protected static Random rand = new Random();
62 static int regionId = 0;
63 protected static Configuration conf;
64 protected static StochasticLoadBalancer loadBalancer;
65
66 @BeforeClass
67 public static void beforeAllTests() throws Exception {
68 conf = HBaseConfiguration.create();
69 conf.setClass("hbase.util.ip.to.rack.determiner", MockMapping.class, DNSToSwitchMapping.class);
70 conf.setFloat("hbase.master.balancer.stochastic.maxMovePercent", 0.75f);
71 conf.setFloat("hbase.regions.slop", 0.0f);
72 conf.setFloat("hbase.master.balancer.stochastic.localityCost", 0);
73 loadBalancer = new StochasticLoadBalancer();
74 loadBalancer.setConf(conf);
75 }
76
77 protected int[] largeCluster = new int[] { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
78 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
79 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
80 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
81 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
82 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
83 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
84 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
85 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
86 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
87 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
88 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
89 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
90 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 56 };
91
92
93 protected int[][] clusterStateMocks = new int[][]{
94
95 new int[]{0},
96 new int[]{1},
97 new int[]{10},
98
99 new int[]{0, 0},
100 new int[]{2, 0},
101 new int[]{2, 1},
102 new int[]{2, 2},
103 new int[]{2, 3},
104 new int[]{2, 4},
105 new int[]{1, 1},
106 new int[]{0, 1},
107 new int[]{10, 1},
108 new int[]{514, 1432},
109 new int[]{48, 53},
110
111 new int[]{0, 1, 2},
112 new int[]{1, 2, 3},
113 new int[]{0, 2, 2},
114 new int[]{0, 3, 0},
115 new int[]{0, 4, 0},
116 new int[]{20, 20, 0},
117
118 new int[]{0, 1, 2, 3},
119 new int[]{4, 0, 0, 0},
120 new int[]{5, 0, 0, 0},
121 new int[]{6, 6, 0, 0},
122 new int[]{6, 2, 0, 0},
123 new int[]{6, 1, 0, 0},
124 new int[]{6, 0, 0, 0},
125 new int[]{4, 4, 4, 7},
126 new int[]{4, 4, 4, 8},
127 new int[]{0, 0, 0, 7},
128
129 new int[]{1, 1, 1, 1, 4},
130
131 new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15},
132 new int[]{0, 0, 0, 0, 0, 0, 0, 0, 0, 10},
133 new int[]{6, 6, 5, 6, 6, 6, 6, 6, 6, 1},
134 new int[]{0, 0, 0, 0, 0, 0, 0, 0, 0, 54},
135 new int[]{0, 0, 0, 0, 0, 0, 0, 0, 0, 55},
136 new int[]{0, 0, 0, 0, 0, 0, 0, 0, 0, 56},
137 new int[]{0, 0, 0, 0, 0, 0, 0, 0, 0, 16},
138 new int[]{1, 1, 1, 1, 1, 1, 1, 1, 1, 8},
139 new int[]{1, 1, 1, 1, 1, 1, 1, 1, 1, 9},
140 new int[]{1, 1, 1, 1, 1, 1, 1, 1, 1, 10},
141 new int[]{1, 1, 1, 1, 1, 1, 1, 1, 1, 123},
142 new int[]{1, 1, 1, 1, 1, 1, 1, 1, 1, 155},
143 new int[]{10, 7, 12, 8, 11, 10, 9, 14},
144 new int[]{13, 14, 6, 10, 10, 10, 8, 10},
145 new int[]{130, 14, 60, 10, 100, 10, 80, 10},
146 new int[]{130, 140, 60, 100, 100, 100, 80, 100},
147 new int[]{0, 5 , 5, 5, 5},
148 largeCluster,
149
150 };
151
152
153 public static class MockMapping implements DNSToSwitchMapping {
154 public MockMapping(Configuration conf) {
155 }
156
157 public List<String> resolve(List<String> names) {
158 List<String> ret = new ArrayList<String>(names.size());
159 for (String name : names) {
160 ret.add("rack");
161 }
162 return ret;
163 }
164
165
166 public void reloadCachedMappings() {
167 }
168
169
170 public void reloadCachedMappings(List<String> arg0) {
171 }
172 }
173
174
175
176
177
178 public void assertClusterAsBalanced(List<ServerAndLoad> servers) {
179 int numServers = servers.size();
180 int numRegions = 0;
181 int maxRegions = 0;
182 int minRegions = Integer.MAX_VALUE;
183 for (ServerAndLoad server : servers) {
184 int nr = server.getLoad();
185 if (nr > maxRegions) {
186 maxRegions = nr;
187 }
188 if (nr < minRegions) {
189 minRegions = nr;
190 }
191 numRegions += nr;
192 }
193 if (maxRegions - minRegions < 2) {
194
195 return;
196 }
197 int min = numRegions / numServers;
198 int max = numRegions % numServers == 0 ? min : min + 1;
199
200 for (ServerAndLoad server : servers) {
201 assertTrue(server.getLoad() >= 0);
202 assertTrue(server.getLoad() <= max);
203 assertTrue(server.getLoad() >= min);
204 }
205 }
206
207
208
209
210 public void assertRegionReplicaPlacement(Map<ServerName, List<HRegionInfo>> serverMap, RackManager rackManager) {
211 TreeMap<String, Set<HRegionInfo>> regionsPerHost = new TreeMap<String, Set<HRegionInfo>>();
212 TreeMap<String, Set<HRegionInfo>> regionsPerRack = new TreeMap<String, Set<HRegionInfo>>();
213
214 for (Entry<ServerName, List<HRegionInfo>> entry : serverMap.entrySet()) {
215 String hostname = entry.getKey().getHostname();
216 Set<HRegionInfo> infos = regionsPerHost.get(hostname);
217 if (infos == null) {
218 infos = new HashSet<HRegionInfo>();
219 regionsPerHost.put(hostname, infos);
220 }
221
222 for (HRegionInfo info : entry.getValue()) {
223 HRegionInfo primaryInfo = RegionReplicaUtil.getRegionInfoForDefaultReplica(info);
224 if (!infos.add(primaryInfo)) {
225 Assert.fail("Two or more region replicas are hosted on the same host after balance");
226 }
227 }
228 }
229
230 if (rackManager == null) {
231 return;
232 }
233
234 for (Entry<ServerName, List<HRegionInfo>> entry : serverMap.entrySet()) {
235 String rack = rackManager.getRack(entry.getKey());
236 Set<HRegionInfo> infos = regionsPerRack.get(rack);
237 if (infos == null) {
238 infos = new HashSet<HRegionInfo>();
239 regionsPerRack.put(rack, infos);
240 }
241
242 for (HRegionInfo info : entry.getValue()) {
243 HRegionInfo primaryInfo = RegionReplicaUtil.getRegionInfoForDefaultReplica(info);
244 if (!infos.add(primaryInfo)) {
245 Assert.fail("Two or more region replicas are hosted on the same rack after balance");
246 }
247 }
248 }
249 }
250
251 protected String printStats(List<ServerAndLoad> servers) {
252 int numServers = servers.size();
253 int totalRegions = 0;
254 for (ServerAndLoad server : servers) {
255 totalRegions += server.getLoad();
256 }
257 float average = (float) totalRegions / numServers;
258 int max = (int) Math.ceil(average);
259 int min = (int) Math.floor(average);
260 return "[srvr=" + numServers + " rgns=" + totalRegions + " avg=" + average + " max=" + max
261 + " min=" + min + "]";
262 }
263
264 protected List<ServerAndLoad> convertToList(final Map<ServerName, List<HRegionInfo>> servers) {
265 List<ServerAndLoad> list = new ArrayList<ServerAndLoad>(servers.size());
266 for (Map.Entry<ServerName, List<HRegionInfo>> e : servers.entrySet()) {
267 list.add(new ServerAndLoad(e.getKey(), e.getValue().size()));
268 }
269 return list;
270 }
271
272 protected String printMock(List<ServerAndLoad> balancedCluster) {
273 SortedSet<ServerAndLoad> sorted = new TreeSet<ServerAndLoad>(balancedCluster);
274 ServerAndLoad[] arr = sorted.toArray(new ServerAndLoad[sorted.size()]);
275 StringBuilder sb = new StringBuilder(sorted.size() * 4 + 4);
276 sb.append("{ ");
277 for (int i = 0; i < arr.length; i++) {
278 if (i != 0) {
279 sb.append(" , ");
280 }
281 sb.append(arr[i].getServerName().getHostname());
282 sb.append(":");
283 sb.append(arr[i].getLoad());
284 }
285 sb.append(" }");
286 return sb.toString();
287 }
288
289
290
291
292
293
294
295
296
297 protected List<ServerAndLoad> reconcile(List<ServerAndLoad> list,
298 List<RegionPlan> plans,
299 Map<ServerName, List<HRegionInfo>> servers) {
300 List<ServerAndLoad> result = new ArrayList<ServerAndLoad>(list.size());
301
302 Map<ServerName, ServerAndLoad> map = new HashMap<ServerName, ServerAndLoad>(list.size());
303 for (ServerAndLoad sl : list) {
304 map.put(sl.getServerName(), sl);
305 }
306 if (plans != null) {
307 for (RegionPlan plan : plans) {
308 ServerName source = plan.getSource();
309
310 updateLoad(map, source, -1);
311 ServerName destination = plan.getDestination();
312 updateLoad(map, destination, +1);
313
314 servers.get(source).remove(plan.getRegionInfo());
315 servers.get(destination).add(plan.getRegionInfo());
316 }
317 }
318 result.clear();
319 result.addAll(map.values());
320 return result;
321 }
322
323 protected void updateLoad(final Map<ServerName, ServerAndLoad> map,
324 final ServerName sn,
325 final int diff) {
326 ServerAndLoad sal = map.get(sn);
327 if (sal == null) sal = new ServerAndLoad(sn, 0);
328 sal = new ServerAndLoad(sn, sal.getLoad() + diff);
329 map.put(sn, sal);
330 }
331
332 protected TreeMap<ServerName, List<HRegionInfo>> mockClusterServers(int[] mockCluster) {
333 return mockClusterServers(mockCluster, -1);
334 }
335
336 protected BaseLoadBalancer.Cluster mockCluster(int[] mockCluster) {
337 return new BaseLoadBalancer.Cluster(
338 mockClusterServers(mockCluster, -1), null, null, null);
339 }
340
341 protected TreeMap<ServerName, List<HRegionInfo>> mockClusterServers(int[] mockCluster, int numTables) {
342 int numServers = mockCluster.length;
343 TreeMap<ServerName, List<HRegionInfo>> servers = new TreeMap<ServerName, List<HRegionInfo>>();
344 for (int i = 0; i < numServers; i++) {
345 int numRegions = mockCluster[i];
346 ServerAndLoad sal = randomServer(0);
347 List<HRegionInfo> regions = randomRegions(numRegions, numTables);
348 servers.put(sal.getServerName(), regions);
349 }
350 return servers;
351 }
352
353 private Queue<HRegionInfo> regionQueue = new LinkedList<HRegionInfo>();
354
355 protected List<HRegionInfo> randomRegions(int numRegions) {
356 return randomRegions(numRegions, -1);
357 }
358
359 protected List<HRegionInfo> randomRegions(int numRegions, int numTables) {
360 List<HRegionInfo> regions = new ArrayList<HRegionInfo>(numRegions);
361 byte[] start = new byte[16];
362 byte[] end = new byte[16];
363 rand.nextBytes(start);
364 rand.nextBytes(end);
365 for (int i = 0; i < numRegions; i++) {
366 if (!regionQueue.isEmpty()) {
367 regions.add(regionQueue.poll());
368 continue;
369 }
370 Bytes.putInt(start, 0, numRegions << 1);
371 Bytes.putInt(end, 0, (numRegions << 1) + 1);
372 TableName tableName =
373 TableName.valueOf("table" + (numTables > 0 ? rand.nextInt(numTables) : i));
374 HRegionInfo hri = new HRegionInfo(tableName, start, end, false, regionId++);
375 regions.add(hri);
376 }
377 return regions;
378 }
379
380 protected void returnRegions(List<HRegionInfo> regions) {
381 regionQueue.addAll(regions);
382 }
383
384 private Queue<ServerName> serverQueue = new LinkedList<ServerName>();
385
386 protected ServerAndLoad randomServer(final int numRegionsPerServer) {
387 if (!this.serverQueue.isEmpty()) {
388 ServerName sn = this.serverQueue.poll();
389 return new ServerAndLoad(sn, numRegionsPerServer);
390 }
391 String host = "srv" + rand.nextInt(Integer.MAX_VALUE);
392 int port = rand.nextInt(60000);
393 long startCode = rand.nextLong();
394 ServerName sn = ServerName.valueOf(host, port, startCode);
395 return new ServerAndLoad(sn, numRegionsPerServer);
396 }
397
398 protected List<ServerAndLoad> randomServers(int numServers, int numRegionsPerServer) {
399 List<ServerAndLoad> servers = new ArrayList<ServerAndLoad>(numServers);
400 for (int i = 0; i < numServers; i++) {
401 servers.add(randomServer(numRegionsPerServer));
402 }
403 return servers;
404 }
405
406 protected void returnServer(ServerName server) {
407 serverQueue.add(server);
408 }
409
410 protected void returnServers(List<ServerName> servers) {
411 this.serverQueue.addAll(servers);
412 }
413
414 protected void testWithCluster(int numNodes,
415 int numRegions,
416 int numRegionsPerServer,
417 int replication,
418 int numTables,
419 boolean assertFullyBalanced, boolean assertFullyBalancedForReplicas) {
420 Map<ServerName, List<HRegionInfo>> serverMap =
421 createServerMap(numNodes, numRegions, numRegionsPerServer, replication, numTables);
422 testWithCluster(serverMap, null, assertFullyBalanced, assertFullyBalancedForReplicas);
423 }
424
425 protected void testWithCluster(Map<ServerName, List<HRegionInfo>> serverMap,
426 RackManager rackManager, boolean assertFullyBalanced, boolean assertFullyBalancedForReplicas) {
427 List<ServerAndLoad> list = convertToList(serverMap);
428 LOG.info("Mock Cluster : " + printMock(list) + " " + printStats(list));
429
430 loadBalancer.setRackManager(rackManager);
431
432 List<RegionPlan> plans = loadBalancer.balanceCluster(serverMap);
433 assertNotNull(plans);
434
435
436 if (assertFullyBalanced || assertFullyBalancedForReplicas) {
437
438 List<ServerAndLoad> balancedCluster = reconcile(list, plans, serverMap);
439
440
441 LOG.info("Mock Balance : " + printMock(balancedCluster));
442
443 if (assertFullyBalanced) {
444 assertClusterAsBalanced(balancedCluster);
445 List<RegionPlan> secondPlans = loadBalancer.balanceCluster(serverMap);
446 assertNull(secondPlans);
447 }
448
449 if (assertFullyBalancedForReplicas) {
450 assertRegionReplicaPlacement(serverMap, rackManager);
451 }
452 }
453 }
454
455 protected Map<ServerName, List<HRegionInfo>> createServerMap(int numNodes,
456 int numRegions,
457 int numRegionsPerServer,
458 int replication,
459 int numTables) {
460
461
462
463 int[] cluster = new int[numNodes];
464 for (int i =0; i < numNodes; i++) {
465 cluster[i] = numRegionsPerServer;
466 }
467 cluster[cluster.length - 1] = numRegions - ((cluster.length - 1) * numRegionsPerServer);
468 Map<ServerName, List<HRegionInfo>> clusterState = mockClusterServers(cluster, numTables);
469 if (replication > 0) {
470
471 for (List<HRegionInfo> regions : clusterState.values()) {
472 int length = regions.size();
473 for (int i = 0; i < length; i++) {
474 for (int r = 1; r < replication ; r++) {
475 regions.add(RegionReplicaUtil.getRegionInfoForReplica(regions.get(i), r));
476 }
477 }
478 }
479 }
480
481 return clusterState;
482 }
483
484 }