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 java.util.ArrayList;
21  import java.util.Arrays;
22  import java.util.List;
23  import java.util.Map;
24  import java.util.Queue;
25  import java.util.TreeMap;
26  
27  import org.apache.commons.logging.Log;
28  import org.apache.commons.logging.LogFactory;
29  import org.apache.hadoop.conf.Configuration;
30  import org.apache.hadoop.hbase.ClusterStatus;
31  import org.apache.hadoop.hbase.HBaseConfiguration;
32  import org.apache.hadoop.hbase.HRegionInfo;
33  import org.apache.hadoop.hbase.MediumTests;
34  import org.apache.hadoop.hbase.RegionLoad;
35  import org.apache.hadoop.hbase.ServerLoad;
36  import org.apache.hadoop.hbase.ServerName;
37  import org.apache.hadoop.hbase.master.RegionPlan;
38  import org.apache.hadoop.hbase.util.Bytes;
39  import org.junit.BeforeClass;
40  import org.junit.Test;
41  import org.junit.experimental.categories.Category;
42  
43  import static org.junit.Assert.assertEquals;
44  import static org.junit.Assert.assertNotNull;
45  import static org.junit.Assert.assertNull;
46  import static org.junit.Assert.assertTrue;
47  import static org.mockito.Mockito.mock;
48  import static org.mockito.Mockito.when;
49  
50  @Category(MediumTests.class)
51  public class TestStochasticLoadBalancer extends BalancerTestBase {
52    public static final String REGION_KEY = "testRegion";
53    private static StochasticLoadBalancer loadBalancer;
54    private static final Log LOG = LogFactory.getLog(TestStochasticLoadBalancer.class);
55  
56    @BeforeClass
57    public static void beforeAllTests() throws Exception {
58      Configuration conf = HBaseConfiguration.create();
59      conf.setFloat("hbase.master.balancer.stochastic.maxMovePercent", 0.75f);
60      loadBalancer = new StochasticLoadBalancer();
61      loadBalancer.setConf(conf);
62    }
63  
64    // int[testnum][servernumber] -> numregions
65    int[][] clusterStateMocks = new int[][]{
66        // 1 node
67        new int[]{0},
68        new int[]{1},
69        new int[]{10},
70        // 2 node
71        new int[]{0, 0},
72        new int[]{2, 0},
73        new int[]{2, 1},
74        new int[]{2, 2},
75        new int[]{2, 3},
76        new int[]{2, 4},
77        new int[]{1, 1},
78        new int[]{0, 1},
79        new int[]{10, 1},
80        new int[]{514, 1432},
81        new int[]{47, 53},
82        // 3 node
83        new int[]{0, 1, 2},
84        new int[]{1, 2, 3},
85        new int[]{0, 2, 2},
86        new int[]{0, 3, 0},
87        new int[]{0, 4, 0},
88        new int[]{20, 20, 0},
89        // 4 node
90        new int[]{0, 1, 2, 3},
91        new int[]{4, 0, 0, 0},
92        new int[]{5, 0, 0, 0},
93        new int[]{6, 6, 0, 0},
94        new int[]{6, 2, 0, 0},
95        new int[]{6, 1, 0, 0},
96        new int[]{6, 0, 0, 0},
97        new int[]{4, 4, 4, 7},
98        new int[]{4, 4, 4, 8},
99        new int[]{0, 0, 0, 7},
100       // 5 node
101       new int[]{1, 1, 1, 1, 4},
102       // more nodes
103       new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15},
104       new int[]{0, 0, 0, 0, 0, 0, 0, 0, 0, 10},
105       new int[]{6, 6, 5, 6, 6, 6, 6, 6, 6, 1},
106       new int[]{0, 0, 0, 0, 0, 0, 0, 0, 0, 54},
107       new int[]{0, 0, 0, 0, 0, 0, 0, 0, 0, 55},
108       new int[]{0, 0, 0, 0, 0, 0, 0, 0, 0, 56},
109       new int[]{0, 0, 0, 0, 0, 0, 0, 0, 0, 16},
110       new int[]{1, 1, 1, 1, 1, 1, 1, 1, 1, 8},
111       new int[]{1, 1, 1, 1, 1, 1, 1, 1, 1, 9},
112       new int[]{1, 1, 1, 1, 1, 1, 1, 1, 1, 10},
113       new int[]{1, 1, 1, 1, 1, 1, 1, 1, 1, 123},
114       new int[]{1, 1, 1, 1, 1, 1, 1, 1, 1, 155},
115       new int[]{10, 7, 12, 8, 11, 10, 9, 14},
116       new int[]{13, 14, 6, 10, 10, 10, 8, 10},
117       new int[]{130, 14, 60, 10, 100, 10, 80, 10},
118       new int[]{130, 140, 60, 100, 100, 100, 80, 100}
119   };
120 
121   @Test
122   public void testKeepRegionLoad() throws Exception {
123 
124     ServerName sn = ServerName.valueOf("test:8080", 100);
125     int numClusterStatusToAdd = 20000;
126     for (int i = 0; i < numClusterStatusToAdd; i++) {
127       ServerLoad sl = mock(ServerLoad.class);
128 
129       RegionLoad rl = mock(RegionLoad.class);
130       when(rl.getStores()).thenReturn(i);
131 
132       Map<byte[], RegionLoad> regionLoadMap =
133           new TreeMap<byte[], RegionLoad>(Bytes.BYTES_COMPARATOR);
134       regionLoadMap.put(Bytes.toBytes(REGION_KEY), rl);
135       when(sl.getRegionsLoad()).thenReturn(regionLoadMap);
136 
137       ClusterStatus clusterStatus = mock(ClusterStatus.class);
138       when(clusterStatus.getServers()).thenReturn(Arrays.asList(sn));
139       when(clusterStatus.getLoad(sn)).thenReturn(sl);
140 
141       loadBalancer.setClusterStatus(clusterStatus);
142     }
143     assertTrue(loadBalancer.loads.get(REGION_KEY) != null);
144     assertTrue(loadBalancer.loads.get(REGION_KEY).size() == 15);
145 
146     Queue<RegionLoad> loads = loadBalancer.loads.get(REGION_KEY);
147     int i = 0;
148     while(loads.size() > 0) {
149       RegionLoad rl = loads.remove();
150       assertEquals(i + (numClusterStatusToAdd - 15), rl.getStores());
151       i ++;
152     }
153   }
154 
155   /**
156    * Test the load balancing algorithm.
157    *
158    * Invariant is that all servers should be hosting either floor(average) or
159    * ceiling(average)
160    *
161    * @throws Exception
162    */
163   @Test
164   public void testBalanceCluster() throws Exception {
165 
166     for (int[] mockCluster : clusterStateMocks) {
167       Map<ServerName, List<HRegionInfo>> servers = mockClusterServers(mockCluster);
168       List<ServerAndLoad> list = convertToList(servers);
169       LOG.info("Mock Cluster : " + printMock(list) + " " + printStats(list));
170       List<RegionPlan> plans = loadBalancer.balanceCluster(servers);
171       List<ServerAndLoad> balancedCluster = reconcile(list, plans, servers);
172       LOG.info("Mock Balance : " + printMock(balancedCluster));
173       assertClusterAsBalanced(balancedCluster);
174       List<RegionPlan> secondPlans =  loadBalancer.balanceCluster(servers);
175       assertNull(secondPlans);
176       for (Map.Entry<ServerName, List<HRegionInfo>> entry : servers.entrySet()) {
177         returnRegions(entry.getValue());
178         returnServer(entry.getKey());
179       }
180     }
181 
182   }
183 
184   @Test
185   public void testSkewCost() {
186     Configuration conf = HBaseConfiguration.create();
187     StochasticLoadBalancer.CostFunction
188         costFunction = new StochasticLoadBalancer.RegionCountSkewCostFunction(conf);
189     for (int[] mockCluster : clusterStateMocks) {
190       double cost = costFunction.cost(mockCluster(mockCluster));
191       assertTrue(cost >= 0);
192       assertTrue(cost <= 1.01);
193     }
194     assertEquals(1,
195         costFunction.cost(mockCluster(new int[]{0, 0, 0, 0, 1})), 0.01);
196     assertEquals(.75,
197         costFunction.cost(mockCluster(new int[]{0, 0, 0, 1, 1})), 0.01);
198     assertEquals(.5,
199         costFunction.cost(mockCluster(new int[]{0, 0, 1, 1, 1})), 0.01);
200     assertEquals(.25,
201         costFunction.cost(mockCluster(new int[]{0, 1, 1, 1, 1})), 0.01);
202     assertEquals(0,
203         costFunction.cost(mockCluster(new int[]{1, 1, 1, 1, 1})), 0.01);
204     assertEquals(0,
205         costFunction.cost(mockCluster(new int[]{10, 10, 10, 10, 10})), 0.01);
206   }
207 
208   @Test
209   public void testTableSkewCost() {
210     Configuration conf = HBaseConfiguration.create();
211     StochasticLoadBalancer.CostFunction
212         costFunction = new StochasticLoadBalancer.TableSkewCostFunction(conf);
213     for (int[] mockCluster : clusterStateMocks) {
214       BaseLoadBalancer.Cluster cluster = mockCluster(mockCluster);
215       double cost = costFunction.cost(cluster);
216       assertTrue(cost >= 0);
217       assertTrue(cost <= 1.01);
218     }
219   }
220 
221   @Test
222   public void testCostFromArray() {
223     Configuration conf = HBaseConfiguration.create();
224     StochasticLoadBalancer.CostFromRegionLoadFunction
225         costFunction = new StochasticLoadBalancer.MemstoreSizeCostFunction(conf);
226 
227     double[] statOne = new double[100];
228     for (int i =0; i < 100; i++) {
229       statOne[i] = 10;
230     }
231     assertEquals(0, costFunction.costFromArray(statOne), 0.01);
232 
233     double[] statTwo= new double[101];
234     for (int i =0; i < 100; i++) {
235       statTwo[i] = 0;
236     }
237     statTwo[100] = 100;
238     assertEquals(1, costFunction.costFromArray(statTwo), 0.01);
239 
240     double[] statThree = new double[200];
241     for (int i =0; i < 100; i++) {
242       statThree[i] = (0);
243       statThree[i+100] = 100;
244     }
245     assertEquals(0.5, costFunction.costFromArray(statThree), 0.01);
246   }
247 
248   @Test(timeout =  60000)
249   public void testLosingRs() throws Exception {
250     int numNodes = 3;
251     int numRegions = 20;
252     int numRegionsPerServer = 3; //all servers except one
253     int numTables = 2;
254 
255     Map<ServerName, List<HRegionInfo>> serverMap =
256         createServerMap(numNodes, numRegions, numRegionsPerServer, numTables);
257     List<ServerAndLoad> list = convertToList(serverMap);
258 
259 
260     List<RegionPlan> plans = loadBalancer.balanceCluster(serverMap);
261     assertNotNull(plans);
262 
263     // Apply the plan to the mock cluster.
264     List<ServerAndLoad> balancedCluster = reconcile(list, plans, serverMap);
265 
266     assertClusterAsBalanced(balancedCluster);
267 
268     ServerName sn = serverMap.keySet().toArray(new ServerName[serverMap.size()])[0];
269 
270     ServerName deadSn = ServerName.valueOf(sn.getHostname(), sn.getPort(), sn.getStartcode() - 100);
271 
272     serverMap.put(deadSn, new ArrayList<HRegionInfo>(0));
273 
274     plans = loadBalancer.balanceCluster(serverMap);
275     assertNull(plans);
276   }
277 
278   @Test (timeout = 60000)
279   public void testSmallCluster() {
280     int numNodes = 10;
281     int numRegions = 1000;
282     int numRegionsPerServer = 40; //all servers except one
283     int numTables = 10;
284     testWithCluster(numNodes, numRegions, numRegionsPerServer, numTables, true);
285   }
286 
287   @Test (timeout = 60000)
288   public void testSmallCluster2() {
289     int numNodes = 20;
290     int numRegions = 2000;
291     int numRegionsPerServer = 40; //all servers except one
292     int numTables = 10;
293     testWithCluster(numNodes, numRegions, numRegionsPerServer, numTables, true);
294   }
295 
296   @Test (timeout = 60000)
297   public void testSmallCluster3() {
298     int numNodes = 20;
299     int numRegions = 2000;
300     int numRegionsPerServer = 1; // all servers except one
301     int numTables = 10;
302     testWithCluster(numNodes, numRegions, numRegionsPerServer, numTables, false /* max moves */);
303   }
304 
305   @Test (timeout = 800000)
306   public void testMidCluster() {
307     int numNodes = 100;
308     int numRegions = 10000;
309     int numRegionsPerServer = 60; // all servers except one
310     int numTables = 40;
311     testWithCluster(numNodes, numRegions, numRegionsPerServer, numTables, true);
312   }
313 
314   @Test (timeout = 800000)
315   public void testMidCluster2() {
316     int numNodes = 200;
317     int numRegions = 100000;
318     int numRegionsPerServer = 40; // all servers except one
319     int numTables = 400;
320     testWithCluster(numNodes,
321         numRegions,
322         numRegionsPerServer,
323         numTables,
324         false /* num large num regions means may not always get to best balance with one run */);
325   }
326 
327 
328   @Test (timeout = 800000)
329   public void testMidCluster3() {
330     int numNodes = 100;
331     int numRegions = 2000;
332     int numRegionsPerServer = 9; // all servers except one
333     int numTables = 110;
334     testWithCluster(numNodes, numRegions, numRegionsPerServer, numTables, true);
335     // TODO(eclark): Make sure that the tables are well distributed.
336   }
337 
338   @Test
339   public void testLargeCluster() {
340     int numNodes = 1000;
341     int numRegions = 100000; //100 regions per RS
342     int numRegionsPerServer = 80; //all servers except one
343     int numTables = 100;
344     testWithCluster(numNodes, numRegions, numRegionsPerServer, numTables, true);
345   }
346 
347   protected void testWithCluster(int numNodes,
348                                  int numRegions,
349                                  int numRegionsPerServer,
350                                  int numTables,
351                                  boolean assertFullyBalanced) {
352     Map<ServerName, List<HRegionInfo>> serverMap =
353         createServerMap(numNodes, numRegions, numRegionsPerServer, numTables);
354 
355     List<ServerAndLoad> list = convertToList(serverMap);
356     LOG.info("Mock Cluster : " + printMock(list) + " " + printStats(list));
357 
358     // Run the balancer.
359     List<RegionPlan> plans = loadBalancer.balanceCluster(serverMap);
360     assertNotNull(plans);
361 
362     // Check to see that this actually got to a stable place.
363     if (assertFullyBalanced) {
364       // Apply the plan to the mock cluster.
365       List<ServerAndLoad> balancedCluster = reconcile(list, plans, serverMap);
366 
367       // Print out the cluster loads to make debugging easier.
368       LOG.info("Mock Balance : " + printMock(balancedCluster));
369       assertClusterAsBalanced(balancedCluster);
370       List<RegionPlan> secondPlans =  loadBalancer.balanceCluster(serverMap);
371       assertNull(secondPlans);
372     }
373   }
374 
375   private Map<ServerName, List<HRegionInfo>> createServerMap(int numNodes,
376                                                              int numRegions,
377                                                              int numRegionsPerServer,
378                                                              int numTables) {
379     //construct a cluster of numNodes, having  a total of numRegions. Each RS will hold
380     //numRegionsPerServer many regions except for the last one, which will host all the
381     //remaining regions
382     int[] cluster = new int[numNodes];
383     for (int i =0; i < numNodes; i++) {
384       cluster[i] = numRegionsPerServer;
385     }
386     cluster[cluster.length - 1] = numRegions - ((cluster.length - 1) * numRegionsPerServer);
387     return mockClusterServers(cluster, numTables);
388   }
389 }