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 StochasticLoadBalancer loadBalancer;
65 protected static Configuration conf;
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 loadBalancer = new StochasticLoadBalancer();
74 loadBalancer.setConf(conf);
75 }
76
77
78 public static class MockMapping implements DNSToSwitchMapping {
79 public MockMapping(Configuration conf) {
80 }
81
82 public List<String> resolve(List<String> names) {
83 List<String> ret = new ArrayList<String>(names.size());
84 for (String name : names) {
85 ret.add("rack");
86 }
87 return ret;
88 }
89
90
91 public void reloadCachedMappings() {
92 }
93
94
95 public void reloadCachedMappings(List<String> arg0) {
96 }
97 }
98
99 protected void testWithCluster(int numNodes,
100 int numRegions,
101 int numRegionsPerServer,
102 int replication,
103 int numTables,
104 boolean assertFullyBalanced, boolean assertFullyBalancedForReplicas) {
105 Map<ServerName, List<HRegionInfo>> serverMap =
106 createServerMap(numNodes, numRegions, numRegionsPerServer, replication, numTables);
107 testWithCluster(serverMap, null, assertFullyBalanced, assertFullyBalancedForReplicas);
108 }
109
110 protected Map<ServerName, List<HRegionInfo>> createServerMap(int numNodes,
111 int numRegions,
112 int numRegionsPerServer,
113 int replication,
114 int numTables) {
115
116
117
118 int[] cluster = new int[numNodes];
119 for (int i =0; i < numNodes; i++) {
120 cluster[i] = numRegionsPerServer;
121 }
122 cluster[cluster.length - 1] = numRegions - ((cluster.length - 1) * numRegionsPerServer);
123 Map<ServerName, List<HRegionInfo>> clusterState = mockClusterServers(cluster, numTables);
124 if (replication > 0) {
125
126 for (List<HRegionInfo> regions : clusterState.values()) {
127 int length = regions.size();
128 for (int i = 0; i < length; i++) {
129 for (int r = 1; r < replication ; r++) {
130 regions.add(RegionReplicaUtil.getRegionInfoForReplica(regions.get(i), r));
131 }
132 }
133 }
134 }
135
136 return clusterState;
137 }
138
139 protected void testWithCluster(Map<ServerName, List<HRegionInfo>> serverMap,
140 RackManager rackManager, boolean assertFullyBalanced, boolean assertFullyBalancedForReplicas) {
141 List<ServerAndLoad> list = convertToList(serverMap);
142 LOG.info("Mock Cluster : " + printMock(list) + " " + printStats(list));
143
144 loadBalancer.setRackManager(rackManager);
145
146 List<RegionPlan> plans = loadBalancer.balanceCluster(serverMap);
147 assertNotNull(plans);
148
149
150 if (assertFullyBalanced || assertFullyBalancedForReplicas) {
151
152 List<ServerAndLoad> balancedCluster = reconcile(list, plans, serverMap);
153
154
155 LOG.info("Mock Balance : " + printMock(balancedCluster));
156
157 if (assertFullyBalanced) {
158 assertClusterAsBalanced(balancedCluster);
159 List<RegionPlan> secondPlans = loadBalancer.balanceCluster(serverMap);
160 assertNull(secondPlans);
161 }
162
163 if (assertFullyBalancedForReplicas) {
164 assertRegionReplicaPlacement(serverMap, rackManager);
165 }
166 }
167 }
168
169
170
171
172
173 public void assertClusterAsBalanced(List<ServerAndLoad> servers) {
174 int numServers = servers.size();
175 int numRegions = 0;
176 int maxRegions = 0;
177 int minRegions = Integer.MAX_VALUE;
178 for (ServerAndLoad server : servers) {
179 int nr = server.getLoad();
180 if (nr > maxRegions) {
181 maxRegions = nr;
182 }
183 if (nr < minRegions) {
184 minRegions = nr;
185 }
186 numRegions += nr;
187 }
188 if (maxRegions - minRegions < 2) {
189
190 return;
191 }
192 int min = numRegions / numServers;
193 int max = numRegions % numServers == 0 ? min : min + 1;
194
195 for (ServerAndLoad server : servers) {
196 assertTrue(server.getLoad() >= 0);
197 assertTrue(server.getLoad() <= max);
198 assertTrue(server.getLoad() >= min);
199 }
200 }
201
202
203
204
205 public void assertRegionReplicaPlacement(Map<ServerName, List<HRegionInfo>> serverMap, RackManager rackManager) {
206 TreeMap<String, Set<HRegionInfo>> regionsPerHost = new TreeMap<String, Set<HRegionInfo>>();
207 TreeMap<String, Set<HRegionInfo>> regionsPerRack = new TreeMap<String, Set<HRegionInfo>>();
208
209 for (Entry<ServerName, List<HRegionInfo>> entry : serverMap.entrySet()) {
210 String hostname = entry.getKey().getHostname();
211 Set<HRegionInfo> infos = regionsPerHost.get(hostname);
212 if (infos == null) {
213 infos = new HashSet<HRegionInfo>();
214 regionsPerHost.put(hostname, infos);
215 }
216
217 for (HRegionInfo info : entry.getValue()) {
218 HRegionInfo primaryInfo = RegionReplicaUtil.getRegionInfoForDefaultReplica(info);
219 if (!infos.add(primaryInfo)) {
220 Assert.fail("Two or more region replicas are hosted on the same host after balance");
221 }
222 }
223 }
224
225 if (rackManager == null) {
226 return;
227 }
228
229 for (Entry<ServerName, List<HRegionInfo>> entry : serverMap.entrySet()) {
230 String rack = rackManager.getRack(entry.getKey());
231 Set<HRegionInfo> infos = regionsPerRack.get(rack);
232 if (infos == null) {
233 infos = new HashSet<HRegionInfo>();
234 regionsPerRack.put(rack, infos);
235 }
236
237 for (HRegionInfo info : entry.getValue()) {
238 HRegionInfo primaryInfo = RegionReplicaUtil.getRegionInfoForDefaultReplica(info);
239 if (!infos.add(primaryInfo)) {
240 Assert.fail("Two or more region replicas are hosted on the same rack after balance");
241 }
242 }
243 }
244 }
245
246 protected String printStats(List<ServerAndLoad> servers) {
247 int numServers = servers.size();
248 int totalRegions = 0;
249 for (ServerAndLoad server : servers) {
250 totalRegions += server.getLoad();
251 }
252 float average = (float) totalRegions / numServers;
253 int max = (int) Math.ceil(average);
254 int min = (int) Math.floor(average);
255 return "[srvr=" + numServers + " rgns=" + totalRegions + " avg=" + average + " max=" + max
256 + " min=" + min + "]";
257 }
258
259 protected List<ServerAndLoad> convertToList(final Map<ServerName, List<HRegionInfo>> servers) {
260 List<ServerAndLoad> list = new ArrayList<ServerAndLoad>(servers.size());
261 for (Map.Entry<ServerName, List<HRegionInfo>> e : servers.entrySet()) {
262 list.add(new ServerAndLoad(e.getKey(), e.getValue().size()));
263 }
264 return list;
265 }
266
267 protected String printMock(List<ServerAndLoad> balancedCluster) {
268 SortedSet<ServerAndLoad> sorted = new TreeSet<ServerAndLoad>(balancedCluster);
269 ServerAndLoad[] arr = sorted.toArray(new ServerAndLoad[sorted.size()]);
270 StringBuilder sb = new StringBuilder(sorted.size() * 4 + 4);
271 sb.append("{ ");
272 for (int i = 0; i < arr.length; i++) {
273 if (i != 0) {
274 sb.append(" , ");
275 }
276 sb.append(arr[i].getServerName().getHostname());
277 sb.append(":");
278 sb.append(arr[i].getLoad());
279 }
280 sb.append(" }");
281 return sb.toString();
282 }
283
284
285
286
287
288
289
290
291
292 protected List<ServerAndLoad> reconcile(List<ServerAndLoad> list,
293 List<RegionPlan> plans,
294 Map<ServerName, List<HRegionInfo>> servers) {
295 List<ServerAndLoad> result = new ArrayList<ServerAndLoad>(list.size());
296
297 Map<ServerName, ServerAndLoad> map = new HashMap<ServerName, ServerAndLoad>(list.size());
298 for (ServerAndLoad sl : list) {
299 map.put(sl.getServerName(), sl);
300 }
301 if (plans != null) {
302 for (RegionPlan plan : plans) {
303 ServerName source = plan.getSource();
304
305 updateLoad(map, source, -1);
306 ServerName destination = plan.getDestination();
307 updateLoad(map, destination, +1);
308
309 servers.get(source).remove(plan.getRegionInfo());
310 servers.get(destination).add(plan.getRegionInfo());
311 }
312 }
313 result.clear();
314 result.addAll(map.values());
315 return result;
316 }
317
318 protected void updateLoad(final Map<ServerName, ServerAndLoad> map,
319 final ServerName sn,
320 final int diff) {
321 ServerAndLoad sal = map.get(sn);
322 if (sal == null) sal = new ServerAndLoad(sn, 0);
323 sal = new ServerAndLoad(sn, sal.getLoad() + diff);
324 map.put(sn, sal);
325 }
326
327 protected TreeMap<ServerName, List<HRegionInfo>> mockClusterServers(int[] mockCluster) {
328 return mockClusterServers(mockCluster, -1);
329 }
330
331 protected BaseLoadBalancer.Cluster mockCluster(int[] mockCluster) {
332 return new BaseLoadBalancer.Cluster(
333 mockClusterServers(mockCluster, -1), null, null, null);
334 }
335
336 protected TreeMap<ServerName, List<HRegionInfo>> mockClusterServers(int[] mockCluster, int numTables) {
337 int numServers = mockCluster.length;
338 TreeMap<ServerName, List<HRegionInfo>> servers = new TreeMap<ServerName, List<HRegionInfo>>();
339 for (int i = 0; i < numServers; i++) {
340 int numRegions = mockCluster[i];
341 ServerAndLoad sal = randomServer(0);
342 List<HRegionInfo> regions = randomRegions(numRegions, numTables);
343 servers.put(sal.getServerName(), regions);
344 }
345 return servers;
346 }
347
348 private Queue<HRegionInfo> regionQueue = new LinkedList<HRegionInfo>();
349
350 protected List<HRegionInfo> randomRegions(int numRegions) {
351 return randomRegions(numRegions, -1);
352 }
353
354 protected List<HRegionInfo> randomRegions(int numRegions, int numTables) {
355 List<HRegionInfo> regions = new ArrayList<HRegionInfo>(numRegions);
356 byte[] start = new byte[16];
357 byte[] end = new byte[16];
358 rand.nextBytes(start);
359 rand.nextBytes(end);
360 for (int i = 0; i < numRegions; i++) {
361 if (!regionQueue.isEmpty()) {
362 regions.add(regionQueue.poll());
363 continue;
364 }
365 Bytes.putInt(start, 0, numRegions << 1);
366 Bytes.putInt(end, 0, (numRegions << 1) + 1);
367 TableName tableName =
368 TableName.valueOf("table" + (numTables > 0 ? rand.nextInt(numTables) : i));
369 HRegionInfo hri = new HRegionInfo(tableName, start, end, false, regionId++);
370 regions.add(hri);
371 }
372 return regions;
373 }
374
375 protected void returnRegions(List<HRegionInfo> regions) {
376 regionQueue.addAll(regions);
377 }
378
379 private Queue<ServerName> serverQueue = new LinkedList<ServerName>();
380
381 protected ServerAndLoad randomServer(final int numRegionsPerServer) {
382 if (!this.serverQueue.isEmpty()) {
383 ServerName sn = this.serverQueue.poll();
384 return new ServerAndLoad(sn, numRegionsPerServer);
385 }
386 String host = "srv" + rand.nextInt(Integer.MAX_VALUE);
387 int port = rand.nextInt(60000);
388 long startCode = rand.nextLong();
389 ServerName sn = ServerName.valueOf(host, port, startCode);
390 return new ServerAndLoad(sn, numRegionsPerServer);
391 }
392
393 protected List<ServerAndLoad> randomServers(int numServers, int numRegionsPerServer) {
394 List<ServerAndLoad> servers = new ArrayList<ServerAndLoad>(numServers);
395 for (int i = 0; i < numServers; i++) {
396 servers.add(randomServer(numRegionsPerServer));
397 }
398 return servers;
399 }
400
401 protected void returnServer(ServerName server) {
402 serverQueue.add(server);
403 }
404
405 protected void returnServers(List<ServerName> servers) {
406 this.serverQueue.addAll(servers);
407 }
408
409 }