View Javadoc

1   /**
2    * Licensed to the Apache Software Foundation (ASF) under one
3    * or more contributor license agreements.  See the NOTICE file
4    * distributed with this work for additional information
5    * regarding copyright ownership.  The ASF licenses this file
6    * to you under the Apache License, Version 2.0 (the
7    * "License"); you may not use this file except in compliance
8    * with the License.  You may obtain a copy of the License at
9    *
10   *     http://www.apache.org/licenses/LICENSE-2.0
11   *
12   * Unless required by applicable law or agreed to in writing, software
13   * distributed under the License is distributed on an "AS IS" BASIS,
14   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15   * See the License for the specific language governing permissions and
16   * limitations under the License.
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   * Class used to be the base of unit tests on load balancers. It gives helper
56   * methods to create maps of {@link ServerName} to lists of {@link HRegionInfo}
57   * and to check list of region plans.
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    // int[testnum][servernumber] -> numregions
94    protected int[][] clusterStateMocks = new int[][]{
95        // 1 node
96        new int[]{0},
97        new int[]{1},
98        new int[]{10},
99        // 2 node
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       // 3 node
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       // 4 node
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       // 5 node
130       new int[]{1, 1, 1, 1, 4},
131       // more nodes
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   // This class is introduced because IP to rack resolution can be lengthy.
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     // do not add @Override annotations here. It mighty break compilation with earlier Hadoops
168     public void reloadCachedMappings() {
169     }
170 
171     // do not add @Override annotations here. It mighty break compilation with earlier Hadoops
172     public void reloadCachedMappings(List<String> arg0) {
173     }
174   }
175 
176   /**
177    * Invariant is that all servers have between floor(avg) and ceiling(avg)
178    * number of regions.
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       // less than 2 between max and min, can't balance
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    * Checks whether region replicas are not hosted on the same host.
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    * This assumes the RegionPlan HSI instances are the same ones in the map, so
293    * actually no need to even pass in the map, but I think it's clearer.
294    *
295    * @param list
296    * @param plans
297    * @return
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     // Run the balancer.
434     List<RegionPlan> plans = loadBalancer.balanceCluster(serverMap);
435     assertNotNull(plans);
436 
437     // Check to see that this actually got to a stable place.
438     if (assertFullyBalanced || assertFullyBalancedForReplicas) {
439       // Apply the plan to the mock cluster.
440       List<ServerAndLoad> balancedCluster = reconcile(list, plans, serverMap);
441 
442       // Print out the cluster loads to make debugging easier.
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     //construct a cluster of numNodes, having  a total of numRegions. Each RS will hold
463     //numRegionsPerServer many regions except for the last one, which will host all the
464     //remaining regions
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       // replicate the regions to the same servers
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 }