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.util.Bytes;
49  import org.apache.hadoop.net.DNSToSwitchMapping;
50  import org.junit.Assert;
51  import org.junit.BeforeClass;
52  
53  /**
54   * Class used to be the base of unit tests on load balancers. It gives helper
55   * methods to create maps of {@link ServerName} to lists of {@link HRegionInfo}
56   * and to check list of region plans.
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    // int[testnum][servernumber] -> numregions
93    protected int[][] clusterStateMocks = new int[][]{
94        // 1 node
95        new int[]{0},
96        new int[]{1},
97        new int[]{10},
98        // 2 node
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       // 3 node
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       // 4 node
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       // 5 node
129       new int[]{1, 1, 1, 1, 4},
130       // more nodes
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   // This class is introduced because IP to rack resolution can be lengthy.
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     // do not add @Override annotations here. It mighty break compilation with earlier Hadoops
166     public void reloadCachedMappings() {
167     }
168 
169     // do not add @Override annotations here. It mighty break compilation with earlier Hadoops
170     public void reloadCachedMappings(List<String> arg0) {
171     }
172   }
173 
174   /**
175    * Invariant is that all servers have between floor(avg) and ceiling(avg)
176    * number of regions.
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       // less than 2 between max and min, can't balance
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    * Checks whether region replicas are not hosted on the same host.
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    * This assumes the RegionPlan HSI instances are the same ones in the map, so
291    * actually no need to even pass in the map, but I think it's clearer.
292    *
293    * @param list
294    * @param plans
295    * @return
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     // Run the balancer.
432     List<RegionPlan> plans = loadBalancer.balanceCluster(serverMap);
433     assertNotNull(plans);
434 
435     // Check to see that this actually got to a stable place.
436     if (assertFullyBalanced || assertFullyBalancedForReplicas) {
437       // Apply the plan to the mock cluster.
438       List<ServerAndLoad> balancedCluster = reconcile(list, plans, serverMap);
439 
440       // Print out the cluster loads to make debugging easier.
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     //construct a cluster of numNodes, having  a total of numRegions. Each RS will hold
461     //numRegionsPerServer many regions except for the last one, which will host all the
462     //remaining regions
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       // replicate the regions to the same servers
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 }