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.assertTrue;
21  
22  import java.util.ArrayList;
23  import java.util.HashMap;
24  import java.util.LinkedList;
25  import java.util.List;
26  import java.util.Map;
27  import java.util.Queue;
28  import java.util.Random;
29  import java.util.SortedSet;
30  import java.util.TreeMap;
31  import java.util.TreeSet;
32  
33  import org.apache.hadoop.hbase.TableName;
34  import org.apache.hadoop.hbase.HRegionInfo;
35  import org.apache.hadoop.hbase.ServerName;
36  import org.apache.hadoop.hbase.master.RegionPlan;
37  import org.apache.hadoop.hbase.util.Bytes;
38  
39  /**
40   * Class used to be the base of unit tests on load balancers. It gives helper
41   * methods to create maps of {@link ServerName} to lists of {@link HRegionInfo}
42   * and to check list of region plans.
43   *
44   */
45  public class BalancerTestBase {
46  
47    protected static Random rand = new Random();
48    static int regionId = 0;
49  
50    /**
51     * Invariant is that all servers have between floor(avg) and ceiling(avg)
52     * number of regions.
53     */
54    public void assertClusterAsBalanced(List<ServerAndLoad> servers) {
55      int numServers = servers.size();
56      int numRegions = 0;
57      int maxRegions = 0;
58      int minRegions = Integer.MAX_VALUE;
59      for (ServerAndLoad server : servers) {
60        int nr = server.getLoad();
61        if (nr > maxRegions) {
62          maxRegions = nr;
63        }
64        if (nr < minRegions) {
65          minRegions = nr;
66        }
67        numRegions += nr;
68      }
69      if (maxRegions - minRegions < 2) {
70        // less than 2 between max and min, can't balance
71        return;
72      }
73      int min = numRegions / numServers;
74      int max = numRegions % numServers == 0 ? min : min + 1;
75  
76      for (ServerAndLoad server : servers) {
77        assertTrue(server.getLoad() >= 0);
78        assertTrue(server.getLoad() <= max);
79        assertTrue(server.getLoad() >= min);
80      }
81    }
82  
83    protected String printStats(List<ServerAndLoad> servers) {
84      int numServers = servers.size();
85      int totalRegions = 0;
86      for (ServerAndLoad server : servers) {
87        totalRegions += server.getLoad();
88      }
89      float average = (float) totalRegions / numServers;
90      int max = (int) Math.ceil(average);
91      int min = (int) Math.floor(average);
92      return "[srvr=" + numServers + " rgns=" + totalRegions + " avg=" + average + " max=" + max
93          + " min=" + min + "]";
94    }
95  
96    protected List<ServerAndLoad> convertToList(final Map<ServerName, List<HRegionInfo>> servers) {
97      List<ServerAndLoad> list = new ArrayList<ServerAndLoad>(servers.size());
98      for (Map.Entry<ServerName, List<HRegionInfo>> e : servers.entrySet()) {
99        list.add(new ServerAndLoad(e.getKey(), e.getValue().size()));
100     }
101     return list;
102   }
103 
104   protected String printMock(List<ServerAndLoad> balancedCluster) {
105     SortedSet<ServerAndLoad> sorted = new TreeSet<ServerAndLoad>(balancedCluster);
106     ServerAndLoad[] arr = sorted.toArray(new ServerAndLoad[sorted.size()]);
107     StringBuilder sb = new StringBuilder(sorted.size() * 4 + 4);
108     sb.append("{ ");
109     for (int i = 0; i < arr.length; i++) {
110       if (i != 0) {
111         sb.append(" , ");
112       }
113       sb.append(arr[i].getServerName().getHostname());
114       sb.append(":");
115       sb.append(arr[i].getLoad());
116     }
117     sb.append(" }");
118     return sb.toString();
119   }
120 
121   /**
122    * This assumes the RegionPlan HSI instances are the same ones in the map, so
123    * actually no need to even pass in the map, but I think it's clearer.
124    *
125    * @param list
126    * @param plans
127    * @return
128    */
129   protected List<ServerAndLoad> reconcile(List<ServerAndLoad> list,
130                                           List<RegionPlan> plans,
131                                           Map<ServerName, List<HRegionInfo>> servers) {
132     List<ServerAndLoad> result = new ArrayList<ServerAndLoad>(list.size());
133     if (plans == null) return result;
134     Map<ServerName, ServerAndLoad> map = new HashMap<ServerName, ServerAndLoad>(list.size());
135     for (ServerAndLoad sl : list) {
136       map.put(sl.getServerName(), sl);
137     }
138     for (RegionPlan plan : plans) {
139       ServerName source = plan.getSource();
140 
141       updateLoad(map, source, -1);
142       ServerName destination = plan.getDestination();
143       updateLoad(map, destination, +1);
144 
145       servers.get(source).remove(plan.getRegionInfo());
146       servers.get(destination).add(plan.getRegionInfo());
147     }
148     result.clear();
149     result.addAll(map.values());
150     return result;
151   }
152 
153   protected void updateLoad(final Map<ServerName, ServerAndLoad> map,
154                             final ServerName sn,
155                             final int diff) {
156     ServerAndLoad sal = map.get(sn);
157     if (sal == null) sal = new ServerAndLoad(sn, 0);
158     sal = new ServerAndLoad(sn, sal.getLoad() + diff);
159     map.put(sn, sal);
160   }
161 
162   protected Map<ServerName, List<HRegionInfo>> mockClusterServers(int[] mockCluster) {
163     return mockClusterServers(mockCluster, -1);
164   }
165 
166   protected BaseLoadBalancer.Cluster mockCluster(int[] mockCluster) {
167     return new BaseLoadBalancer.Cluster(mockClusterServers(mockCluster, -1), null, null);
168   }
169 
170   protected Map<ServerName, List<HRegionInfo>> mockClusterServers(int[] mockCluster, int numTables) {
171     int numServers = mockCluster.length;
172     Map<ServerName, List<HRegionInfo>> servers = new TreeMap<ServerName, List<HRegionInfo>>();
173     for (int i = 0; i < numServers; i++) {
174       int numRegions = mockCluster[i];
175       ServerAndLoad sal = randomServer(0);
176       List<HRegionInfo> regions = randomRegions(numRegions, numTables);
177       servers.put(sal.getServerName(), regions);
178     }
179     return servers;
180   }
181 
182   private Queue<HRegionInfo> regionQueue = new LinkedList<HRegionInfo>();
183 
184   protected List<HRegionInfo> randomRegions(int numRegions) {
185     return randomRegions(numRegions, -1);
186   }
187 
188   protected List<HRegionInfo> randomRegions(int numRegions, int numTables) {
189     List<HRegionInfo> regions = new ArrayList<HRegionInfo>(numRegions);
190     byte[] start = new byte[16];
191     byte[] end = new byte[16];
192     rand.nextBytes(start);
193     rand.nextBytes(end);
194     for (int i = 0; i < numRegions; i++) {
195       if (!regionQueue.isEmpty()) {
196         regions.add(regionQueue.poll());
197         continue;
198       }
199       Bytes.putInt(start, 0, numRegions << 1);
200       Bytes.putInt(end, 0, (numRegions << 1) + 1);
201       TableName tableName =
202           TableName.valueOf("table" + (numTables > 0 ? rand.nextInt(numTables) : i));
203       HRegionInfo hri = new HRegionInfo(tableName, start, end, false, regionId++);
204       regions.add(hri);
205     }
206     return regions;
207   }
208 
209   protected void returnRegions(List<HRegionInfo> regions) {
210     regionQueue.addAll(regions);
211   }
212 
213   private Queue<ServerName> serverQueue = new LinkedList<ServerName>();
214 
215   protected ServerAndLoad randomServer(final int numRegionsPerServer) {
216     if (!this.serverQueue.isEmpty()) {
217       ServerName sn = this.serverQueue.poll();
218       return new ServerAndLoad(sn, numRegionsPerServer);
219     }
220     String host = "srv" + rand.nextInt(100000);
221     int port = rand.nextInt(60000);
222     long startCode = rand.nextLong();
223     ServerName sn = ServerName.valueOf(host, port, startCode);
224     return new ServerAndLoad(sn, numRegionsPerServer);
225   }
226 
227   protected List<ServerAndLoad> randomServers(int numServers, int numRegionsPerServer) {
228     List<ServerAndLoad> servers = new ArrayList<ServerAndLoad>(numServers);
229     for (int i = 0; i < numServers; i++) {
230       servers.add(randomServer(numRegionsPerServer));
231     }
232     return servers;
233   }
234 
235   protected void returnServer(ServerName server) {
236     serverQueue.add(server);
237   }
238 
239   protected void returnServers(List<ServerName> servers) {
240     this.serverQueue.addAll(servers);
241   }
242 
243 }