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