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 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    // This class is introduced because IP to rack resolution can be lengthy.
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      // do not add @Override annotations here. It mighty break compilation with earlier Hadoops
91      public void reloadCachedMappings() {
92      }
93  
94      // do not add @Override annotations here. It mighty break compilation with earlier Hadoops
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     //construct a cluster of numNodes, having  a total of numRegions. Each RS will hold
116     //numRegionsPerServer many regions except for the last one, which will host all the
117     //remaining regions
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       // replicate the regions to the same servers
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     // Run the balancer.
146     List<RegionPlan> plans = loadBalancer.balanceCluster(serverMap);
147     assertNotNull(plans);
148 
149     // Check to see that this actually got to a stable place.
150     if (assertFullyBalanced || assertFullyBalancedForReplicas) {
151       // Apply the plan to the mock cluster.
152       List<ServerAndLoad> balancedCluster = reconcile(list, plans, serverMap);
153 
154       // Print out the cluster loads to make debugging easier.
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    * Invariant is that all servers have between floor(avg) and ceiling(avg)
171    * number of regions.
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       // less than 2 between max and min, can't balance
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    * Checks whether region replicas are not hosted on the same host.
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    * This assumes the RegionPlan HSI instances are the same ones in the map, so
286    * actually no need to even pass in the map, but I think it's clearer.
287    *
288    * @param list
289    * @param plans
290    * @return
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 }